使用单调栈的直觉背后的原理

Question

使用单调栈的直觉背后的原理

15

我正在解决 LeetCode.com 上的一个问题：

给定整数数组 A，找到 min(B) 的和，其中 B 是 A 的每个（连续）子数组。由于答案可能很大，请返回模 10^9+7 的答案。

输入：[3,1,2,4]
输出：17
说明：子数组为 [3]、[1]、[2]、[4]、[3,1]、[1,2]、[2,4]、[3,1,2]、[1,2,4]、[3,1,2,4]。最小值分别为 3、1、2、4、1、1、2、1、1、1。总和为 17。

一个点赞量较高的解决方案如下：

class Solution {
public:
  int sumSubarrayMins(vector<int>& A) {
    stack<pair<int, int>> in_stk_p, in_stk_n;
    // left is for the distance to previous less element
    // right is for the distance to next less element
    vector<int> left(A.size()), right(A.size());

    //initialize
    for(int i = 0; i < A.size(); i++) left[i] =  i + 1;
    for(int i = 0; i < A.size(); i++) right[i] = A.size() - i;

    for(int i = 0; i < A.size(); i++){
      // for previous less
      while(!in_stk_p.empty() && in_stk_p.top().first > A[i]) in_stk_p.pop();
      left[i] = in_stk_p.empty()? i + 1: i - in_stk_p.top().second;
      in_stk_p.push({A[i],i});

      // for next less
      while(!in_stk_n.empty() && in_stk_n.top().first > A[i]){
        auto x = in_stk_n.top();in_stk_n.pop();
        right[x.second] = i - x.second;
      }
      in_stk_n.push({A[i], i});
    }

    int ans = 0, mod = 1e9 +7;
    for(int i = 0; i < A.size(); i++){
      ans = (ans + A[i]*left[i]*right[i])%mod;
    }
    return ans;
  }
};

我的问题是：为什么要使用单调递增的栈？它如何帮助计算各个子数组中的最小值？

- J. Doe

栈不是单调递增的，我在代码中看到了两个弹出操作，每个栈都有一个。 - maraca

一个“单调栈”，我想你只能意思是“单调递增”的，这是一个自相矛盾的说法。一旦你从中取出一个元素，它就会减少。不清楚你在问什么。 - user207421

5

@user207421，我认为我的主要问题不在于我们是否应该称其为“单调栈”或“单调递增栈” - 更重要的是为什么首先要使用栈。它如何帮助我们实现我们所追求的目标。 - J. Doe

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Davis Herring · Accepted Answer

将数组可视化为线图，局部最小值为谷底。每个值都与一个范围相关，该范围从前一个较小值之后（如果有的话）延伸到下一个较小值之前（如果有的话）。即使考虑包含它的单元素子数组时，比其邻居大的值也很重要。变量left和right跟踪该范围。

认识到每个方向上比其大的值都会被“遮蔽”，堆栈会维护两个目的的先前未被遮蔽的最小值列表：确定新小数的范围向后延伸了多远，并且（同时）无效的最小值范围向前延伸了多远。代码为每个目的使用单独的堆栈，但没有必要：在（外部）循环的每次迭代之后，它们具有相同的内容。