如何用O(N)时间寻找数组中m(I,J)*子数组长度的最大值

核心思路：找到每个元素作为子数组最小值时的最大覆盖区间，计算该元素值乘以区间长度，最终取所有结果中的最大值。因为当元素是某区间的最小值时，最长区间对应的乘积一定是该元素能贡献的最大值——更短的子数组只会让乘积更小，无需额外计算。

具体步骤 #

• 预处理左右边界：

  • left[i]：数组中第i个元素左边第一个比它小的元素的索引，若不存在则设为-1
  • right[i]：数组中第i个元素右边第一个小于等于它的元素的索引，若不存在则设为数组长度n
    （右边用「小于等于」是为了避免多个相同值元素重复计算同一区间，保证每个区间只对应一个最小值）

• 用单调栈计算边界：
  单调栈能在O(N)时间内完成边界计算，因为每个元素仅入栈和出栈一次：

  1. 计算left数组：维护一个单调递增栈（栈中保存索引，对应元素值递增）。遍历数组时，弹出栈顶所有大于等于当前元素的索引，剩余栈顶就是left[i]，再将当前索引压入栈。
  2. 计算right数组：同样用单调递增栈，从数组末尾往前遍历。弹出栈顶所有大于当前元素的索引，剩余栈顶就是right[i]，再将当前索引压入栈。

• 计算最大乘积：遍历每个元素，计算A[i] * (right[i] - left[i] - 1)，记录最大值。

代码实现（Python） #

def max_min_subarray_product(A):
    n = len(A)
    if n == 0:
        return 0
    
    left = [-1] * n
    stack = []
    # 计算左边界
    for i in range(n):
        while stack and A[stack[-1]] >= A[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)
    
    right = [n] * n
    stack = []
    # 计算右边界
    for i in range(n-1, -1, -1):
        while stack and A[stack[-1]] > A[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)
    
    max_result = 0
    for i in range(n):
        current = A[i] * (right[i] - left[i] - 1)
        if current > max_result:
            max_result = current
    return max_result

复杂度说明 #

整个过程中，每个元素入栈、出栈各一次，边界计算是O(N)；最后遍历计算最大值也是O(N)，因此整体时间复杂度为O(N)，满足要求。

内容的提问来源于stack exchange，提问作者kryomaxim