国美电器如何进行网站的建设与维护,网站的跳出率,苏州市建设局网站首页,vi设计公司1.单调栈 单调栈是一种数据结构#xff0c;其中存放的数据应该是有序的#xff0c;所以单调栈也有单调递减栈和单调递增栈
单调递增栈#xff1a;栈顶到栈底的元素大小是从小到大
单调递减栈#xff1a;栈顶到栈底的元素大小是从大到小 单调栈主要就是用来求一个给定序列中…1.单调栈 单调栈是一种数据结构其中存放的数据应该是有序的所以单调栈也有单调递减栈和单调递增栈
单调递增栈栈顶到栈底的元素大小是从小到大
单调递减栈栈顶到栈底的元素大小是从大到小 单调栈主要就是用来求一个给定序列中每个数左边离它最近的比它大或小的数。如果找的是比它小的数就是构造一个单调递减栈如果找的是比它大的数那构造的就是一个单调递增栈。
2.单调栈模拟 假如我们现在有一个序列1028513我们要找每个数离它最近的比它大的数我们要构造一个单调递增的栈则如果栈为空或者入栈的元素大小小于栈顶值就入栈否则入栈会破坏栈的单调性这时候比入栈元素小的元素全部出栈。 10入栈时栈为空直接入栈栈有一个元素10 2入栈时栈顶元素10比2大则入栈栈内元素为10和2 8入栈时栈顶元素2比8小则栈顶元素出栈此时栈顶元素为10比8大8可以入栈栈内元素为10和8 5入栈时栈顶8比5大可以入栈栈内元素为1085 13入栈时栈顶元素5比13小出栈8比13小出栈10比13小出栈最后栈为空13入栈栈内只有12。 单调递减栈的原理和递增类似
代码
C:
//构造单调递增栈
int top0
for(int i0;in;i)
{if(top0||stk[top]i}{stk[top]i;//当前元素入栈}else{while(topstk[top]i){top--;//出栈}stk[top]i;//当前元素入栈}
}//构造单调递减栈
int top0
for(int i0;in;i)
{if(top0||stk[top]i}{stk[top]i;//当前元素入栈}else{while(topstk[top]i){top--;//出栈}stk[top]i;//当前元素入栈}
}C:
//构造单调递增栈
stackintstk;
for(int i0;in;i)
{while(!stk.empty()stk.top()i){stk.pop()}stk.push(i);
}//构造单调递减栈
stackintstk;
for(int i0;in;i)
{while(!stk.empty()stk.top()i){stk.pop()}stk.push(i);
} 3.单调栈应用(C) 其实我们可以看到这也是类似最近匹配的问题栈最擅长这种问题了
3.1 每日温度 vectorint dailyTemperatures(vectorint temperatures) {vectorint res(temperatures.size(), 0);stackint stk;for (int i 0; i temperatures.size(); i) {while (!stk.empty() temperatures[stk.top()] temperatures[i]) {res[stk.top()] i - stk.top();stk.pop();}stk.push(i);}return res;} 给定一个温度序列让你求每个温度离它最近的比它高的温度是之后第几天显然符合单调递增栈的特征我们定义一个栈stk来存储每个温度对应的下标和存储结果的vector数组res从头开始遍历如果栈为空或者栈顶下标对应的温度大于当前温度值则当前温度对应的下标入栈如果不为空且栈顶下标对应的温度小于当前温度值说明我们找到了这个温度离它最近的比它高的温度值那我们就把两个温度对应天数的差值放入res数组中即res[stk.top()]i-stk.top()然后再让栈顶元素出栈把这个温度对应的下标入栈即可最后返回结果数组res。
3.2 接雨水 int trap(vectorint height) {int ans0;stackintst;for(int i0;iheight.size();i){while(!st.empty()height[st.top()]height[i]){int curst.top();st.pop();if(st.empty())break;int lst.top();int ri;int hmin(height[l],height[r])-height[cur];ans(r-l-1)*h;}st.push(i);}return ans;} 这是一个单调递减栈当我们找到一根比前面高的柱子时就可以计算接到的雨水了。更低的柱子我们就入栈当出现高于栈顶的柱子时我们就可以计算已经接到的雨水然后出栈把当前当前的柱子入栈。 需要注意的是雨水的右边r是当前的索引i底部是栈顶st.top()因为遇到了更高的柱子所以雨水的左边即将出栈使用cur来记录它l就是新的栈顶这样雨水的区域就确定了高度就是左右两边更低的一边减去底部宽度就是左右中间。
