我正在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。
甲高度upvoted溶液是如下：
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;
}
};
我的问题是：为此使用单调递增堆栈的直觉是什么？它如何帮助计算各个子阵列中的最小值？
将数组可视化为线形图，其中（局部）最小值为谷值。每个值是相关的范围内，从刚下一个较小的值（如果有的话）之前，前一个较小的值（如果有的话），只是后延伸。（在考虑包含该值的单子数组时left，即使大于它的邻居值也很重要。）变量并right跟踪该范围。
认识到一个值会分别遮蔽每个方向上大于每个值的每个值，因此堆栈会维护一个先前未遮盖的最小值的列表，其用途有两个：确定新小数位范围的扩展范围和（同时）向前扩展的范围无效的最小值范围扩大。该代码为每个目的使用了一个单独的堆栈，但是没有必要：在（外部）循环的每次迭代之后，每个内容都具有相同的内容。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句