本文介绍了使用单调堆栈背后的直觉的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在解决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。
Ahighly 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;
}
};
我的问题是:为此使用单调递增堆栈背后的直觉是什么?它如何帮助计算各种子数组中的最小值?
推荐答案
将数组可视化为折线图,将(局部)最小值作为山谷。每个值都与范围相关,该范围从上一个较小的值(如果有)之后延伸到下一个较小的值(如果有)之前。(在考虑包含该值的单个子数组时,即使值大于其相邻值也很重要。)变量left
和right
跟踪该范围。
认识到值分别隐藏了每个方向上大于它的每个值,堆栈出于两个目的维护了以前未隐藏的最小值的列表:标识新小数字的范围向后延伸了多远,以及(同时)使失效的最小值的范围向前延伸了多远。代码为每个目的使用单独的堆栈,但没有必要:每个堆栈在(外部)循环的每次迭代后都具有相同的内容。
这篇关于使用单调堆栈背后的直觉的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!
本站部分内容来源互联网,如果有图片或者内容侵犯您的权益请联系我们删除!