直觉背后使用单调堆栈

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。

highly upvoted solution如下：

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跟踪该范围。

识别出一个值分别隐藏每个方向上大于每个方向的值，该堆栈保留了一个先前的，没有阴影的最小值的列表，用于两个目的：识别新的小数字范围延伸的距离和（同时）向前多远无效的最小值范围扩展。代码为每个目的使用单独的堆栈，但是没有必要：每次迭代（外部）循环后每个都有相同的内容。