使用单调堆栈背后的直觉

Question

我正在解决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;
  }
};

我的问题是：为此使用单调递增堆栈背后的直觉是什么？它如何帮助计算各种子阵列中的最小值？

Answer 1

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

认识到一个值阴影在单独的每个方向上比它的每一个值时，堆栈维持以前的，未投影极小的名单有两个目的：确定如何追溯到一个新的小号码的范围延伸，（同时）如何靠前的无效最小值的范围扩展。代码为每个目的使用单独的堆栈，但没有必要：在（外部）循环的每次迭代之后，每个堆栈都具有相同的内容。