统计所选元素为最大值的子数组的个数

Question

我们有一个整数数组X。任务是返回一个Y相同大小的数组，其中ith的元素是具有该元素的最大Y子数组的计数。ithX

例如：

X: [8, 7, 1, 12, 11, 4, 10, 2, 3, 6, 9]
Y: [3, 2, 1, 32, 7, 1, 10, 1, 2, 3, 4]

这是我的解决方案，时间复杂度为二次。

X: [8, 7, 1, 12, 11, 4, 10, 2, 3, 6, 9]
Y: [3, 2, 1, 32, 7, 1, 10, 1, 2, 3, 4]

这个想法是，当元素大于当前元素时，我们使用两个指针向左和向右移动。一旦我们有了当前元素为 max 的数组，我们就可以通过以下方式获取子数组的数量(start_index) * (end_index - start_index + 1)

该算法必须在非常大的测试用例上运行。如何将时间复杂度至少降低到NlogN？

Answer 1

这是一个O(n)版本。代码中的一条注释应该可以使这个想法非常清晰。

JavaScript 代码：

// Preprocess previous higher and lower elements in O(n)
// Adapted from https://www.geeksforgeeks.org/next-greater-element
function prev(A, higherOrLower) {
  function compare(a, b){
    if (higherOrLower == 'higher')
      return a < b
    else if (higherOrLower == 'lower')
      return a > b
  }
  
  let result = new Array(A.length)
  let stack = [A.length - 1]

  for (let i=A.length-2; i>=0; i--){ 
    if (!stack.length){ 
      stack.push(A[i])
      continue
    }

    while (stack.length && compare(A[ stack[stack.length-1] ], A[i]))
      result[ stack.pop() ] = i

    stack.push(i)
  }

  while (stack.length)
    result[ stack.pop() ] = -1

  return result
}

function f(A){
  let prevHigher = prev(A, 'higher')
  let nextHigher = prev(
    A.slice().reverse(), 'higher')
    .map(x => A.length - x - 1)
    .reverse()
  let result = new Array(A.length)
  
  for (let i=0; i<A.length; i++)
    result[i] =
      (i - prevHigher[i]) * (nextHigher[i] - i)
              
  return result
}

var A = [8, 7, 1, 12, 11, 4, 10, 2, 3, 6, 9]

console.log(JSON.stringify(A))
console.log(JSON.stringify(f(A)))