python - 计算所选元素为最大值的子数组的数量

Question

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

例如:

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

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

def solve(A):

    def expand(i):
        left, right = i, i
        while left > 0 and A[i] >= A[left - 1]:
            left -= 1

        while right < len(A) - 1 and A[i] >= A[right + 1]:
            right += 1

        length = right - left + 1
        mid = i - left
        return (mid + 1) * (length - mid)

    result = [0] * len(A)
    MOD = 10**9 + 7
    for i in range(len(A)):
        count = expand(i)
        count %= MOD
        result[i] = count

    return result

这个想法是我们使用两个指针向左和向右移动，而元素大于当前元素。一旦我们有了当前元素最大的数组，我们可以通过 (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)))