本文讲解一个特殊的数据结构：单调栈
看完本文，可以顺势完成以下题目
.下一个更大元素Ⅱ(中等)
.每日温度(中等)
下面我们就结合这两道题来看一看什么是单调栈吧！
一、典例一：下一个更大元素Ⅱ
①题目描述
给你一个循环数组，输出每一个元素的下一个更大的元素，如果这个元素没有他的下一个更大的数字，就返回-1
②示例：
需要注意：最后的1对应的不是-1而是2了。
③思路和单调栈解法的解析
第一反应：暴力法，直接遍历？
可以，但是。。。
如果这样的话，时间复杂度真的太高了：O(n^2)
下面我们来看
首先，抽象所给的数据1、我们把提供的数组抽象一下，想象为高度等比例的几个柱子
2、设想从当前柱子的高度，从前向后看，能看到的第一个柱子，就是我们需要寻找的值了
3、使用单调栈，每一次有新元素加入的时候，进行处理，保持栈内的元素是单调的；新元素进来的时候，结合上图从前往后看，看不见的元素都出栈。
4、栈是先进后出的，而且是找“第一个大的”，就是栈中最小的；所以，使用一个单调减的单调栈(栈顶的最小~)
5、由于使用栈，栈是先进后出的；从后面开始遍历，倒过来入栈,最后栈出来的顺序才是和原数组的顺序是一样的；
④同时我们应该注意以下两点
1、单调栈中存的是什么？
动态的看，是：(从当前位置)从前往后，第一个看见的柱子，第二个看见的柱子，第三个看见的柱子····如此；因为两个高个子柱子中间的那一个柱子，从前面肯定是看不到的；
为什么要强调是看的见的？因为看不见的元素，此时都已经出栈了呀~
2、上图中3对应的res是4，这里是怎么处理循环数组的？
循环数组的巧妙处理：
第一步：做好for()循环的条件控制，i=2*n-1;看起来就是遍历了两次数组一样；
第二步：做好正确读取对应的值（取余%）nums[i%n]；
这样就没必要去双倍扩充数组了！
⑤解题框架与代码：
解题框架：
for(从后往前遍历){循环数组处理：i=2*n-1;nums[i%n]while(){新元素进来，排序一次;被挡住看不见的就出栈}判断{如果栈空，没更大的了，输出-1；否则；输出栈顶元素}新元素来，进栈}
随后就能够写出解题代码了：
classSolution{public:vectorintnextGreaterElements(vectorintnums){intn=nums.size();vectorintres(n);stackints;//单调栈解法和题每日温度相似；多了循环数组的处理//不去增倍数组，使用循环数组；//循环数组，只是索引i变大了，所以for循环里面效果似乎是两次//处理的时候，nums[i%n]就是读取到真的数字for(inti=2*n-1;i=0;i--){while(!s.empty()s.top()=nums[i%n]){s.pop();//反正挡住了，就出栈，保持单调}res[i%n]=s.empty()?-1:s.top();s.push(nums[i%n]);//进新的以便后一步判断}returnres;}};
二、典例二：每日温度
①题目描述
给你一个列表，存放的是未来几天的温度，对应输出，下一个温度更高的天数距离现在几天？如果往后都没温度更高的了，输出0
通俗一点就是，从当前开始，往后看，看到升温的那一天目前需要等多久~
②解析
和上一题差不多，不过需要注意的是，返回的不是元素的值了，而是对应的距离，所以需要调整一下，数组存放的应该是索引
③代码
有了上面的铺垫，直接上代码了
classSolution{public:vectorintdailyTemperatures(vectorintT){vectorintres(T.size());//存放的是索引stackints;//使用单调栈for(inti=T.size()-1;i=0;i--){while(!s.empty()T[s.top()]=T){s.pop();}res=s.empty()?0:(s.top()-i);//s.top()-i就是距离了s.push(i);}returnres;}};预览时标签不可点收录于话题#个上一篇下一篇