第一周训练题单–stack的运用引言​ 这个stack在没学之前感觉没啥大用处在专门学了之后发现也是受益匪浅啊就像是单调栈这个思想我之前是一点都不知道的所以感觉还是很有必要来认真学一学了-_- !萌新选手大佬轻锤当然了如果有一定基础的我们可以不看前面的基础题目首先我们先引用一个最常见的例子栈我们常见的–括号匹配问题题目思路想要实现有效的括号匹配我们就可以巧妙运用stack的特性先进后出的原则我们把所有左括号放进stack里面然后遇到右括号就匹配stack里面的top匹配对了就仍一个最后看看是否是空的栈这题就结束了代码bool isValid(string s) { if(s.size()%2!0) return false; stackchar st; for(auto c:s) { if(c(||c{||c[){ st.push(c); }else{ if(st.empty()) return false; char chst.top(); if(c)ch(||c]ch[||c}ch{){ st.pop(); }else return false; } } if(st.empty()) return true; else return false; }一个基础题我们来打打手了解到了stack的特性那么现在我们就开始进一步的加强吧题目思路这题的话就来到了我们要学习的单调栈的应用了题目说的很清楚要求我们输出每一个数字右边的第一个大于它的数字那么我们就可以用单调栈的性质来解决我们让想要判断的我数字放进栈里面然后找到一个大于它的数字就退出一个同时呢我们用一个哈希来存储每个数字的比它打大的数字最后我们输出数组的时候在哈希里面找就可以了。思路明确了之后呢我们要知道一些函数比如说count函数运用然后要知道哈希怎么用这些就不在这里解释不太了解的可以搜索了解下。代码vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { stackint st; unordered_mapint,int mp; for(auto x:nums2) { while(!st.empty()st.top()x) { mp[st.top()]x; st.pop(); } st.push(x); } vectorint ans; for(auto x:nums1) { if(mp.count(x)) ans.push_back(mp[x]); else ans.push_back(-1); } return ans; }其中while循环就是单调栈的实现只要x一直大于栈顶那么就一直弹出并记录。这题就算是进阶的题目了学会单调栈的应用。但有些人还是感觉太简单了怎么办别急我们一步一步来接下来呢我们学习一个还像是单调栈的题但是呢有些变种的感觉题目思路通过观察的话我们发现这不还是单调栈嘛对确实是但是有些不同的是表示方法看看你是否能观察出来这里就不细说了代码呈下vectorint dailyTemperatures(vectorint temperatures) { int lengthtemperatures.size(); stackint st; vectorint ans(length,0); for(int i0;ilength;i) { while(!st.empty()temperatures[i]temperatures[st.top()]) { int shust.top(); st.pop(); ans[shu]i-shu; } st.push(i); } return ans; }这题也挺有意思的像是一的变种但是呢我们还得仔细想想怎么做题目思路这个题我们看完就感觉还是括号匹配唯一不同的就是求得分数而分数又不太好表示。仔细观察发现这个形式要么就是()()形式要么就是(())形式也就是说要么是并列关系要么就是包含关系那么我们可以吧左括号放进去遇到右括号得时候呢我们取出来一个栈头看看这个数字是不是0要是0就是单独存在它属于第一种并列关系那么头加一要是不是0那么就是我们说的包含关系也就是乘2这样题解就出来了代码int scoreOfParentheses(string s) { stackint st; st.push(0); for(auto c:s) { if(c() st.push(0); else{ int cntst.top(); st.pop(); if(cnt0){ st.top()1; }else{ st.top()(2*cnt); } } } return st.top(); }这其实挺有意思的观察出来并列与包含的关系题解就出来了。值得注意的是在操作之前我们需要给栈先加一个0进去因为开始分数是0这个必须得注意没有这个其他程序是实现不了的上面的题看着挺爽的下面再来一道和这个题又有点像的题。题目思路这题就比较有意思了看着和上一题也是十分相似但是呢他要长度又怎么办呢这时候我们可以用到这个lr之间的距离公式了l和r距离是r-l1,那么我们可以把不符合有效括号的下标都扔进栈里面我们找到合适的就扔出来然后比较大小听着其实听抽象的跟着代码来理解就好了代码int longestValidParentheses(string s) { stackint st; st.push(-1); int ans0; for(int i0;is.size();i) { if(s[i](){ st.push(i); }else{ st.pop(); if(st.empty()) st.push(i); else ansmax(ans,i-st.top()); } } return ans; }这里的开始同样也是十分重要的我们需要初始化一个-1因为如果碰到了()了我们的栈肯定不能空下去那就把第一个下标的前面那个下标存进去这里面就是栈其实尽可能的只存左括号但是不符合的右括号也得存进去这样我们可以有效的算出来后面可以有效的长度这个题重在理解难度其实不算太大吃透了基本上就能运用好栈了最后再来一题检验成果可能有点难理解慢慢来。题目思路这题其实还是栈的应用好像也是可以用单调栈来解决的这里我们就不用单调栈了用一个另一种方法–动态规划单调栈的方法可以补充。这一题的思路就是通过两个算是指针吧左指针画一个区域也就是左边尽可能大的区域然后右指针也画一个区域也就是右边尽可能达到的区域然后我们取这两个区域的交集这个交集就是答案那么根据这个图其实就很明显了解到了这个方法的解法了就通过两个数组求交集的方法就可以代码int trap(vectorint height) { int lengthheight.size(); vectorint lmax(length); vectorint rmax(length); lmax[0]height[0]; rmax[length-1]height[length-1]; for(int i1;ilength;i) { lmax[i]max(lmax[i-1],height[i]); rmax[length-i-1]max(rmax[length-i],height[length-i-1]); } int ans0; for(int i0;ilength;i) { ansmin(lmax[i],rmax[i])-height[i]; } return ans; }l就表示左边的数组r就表示右边的数组然后我们找左数组的时候从左到右来找找右数组的时候从右边找都找最大值(也就是我之前说的取得最大区域)最后我们的答案就是累加这个左数组和有数组的最小值减去本来的地高就是每块的水量总结​其实stack的应用东西挺多慢慢搜索但是学过这么多其实也能完成大多数题了重在思维多练多学相信哪个算法都不是难题​希望本篇文章对比有帮助-_-