对于栈这种数据结构,相信大部分同学都会觉得很简单,它只有一个特性,那就是先进后出。
本篇我们来看一个特殊的栈结构,也就是单调栈。单调栈顾名思义,就是栈里面的数据是有序的,比如栈1、2、3,而1、3、2就不是有序的,单调栈可以是升序,也可以是降序。
leetcode上面有近10题是单调栈的解法,如下图所示:
今天我们就来看第一题经典单调栈问题,leetcode 739.每日温度。
请根据每日气温列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。
例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
就是给定一个列表A,对于A中每个元素e,找出比e更大元素b(注意b在e后面),计算e和b的距离。
这个题目就像一个队列排队,每个元素高矮不一,从前往后,每个人看到的比自己高的就算一下和那个人的距离。
而这个题目如何与栈挂钩呢?
我们假设栈里面的人都很势力,只和比自己高的人做朋友,栈顶元素遇到高的就出栈。
从第一个人开始入栈,如果栈顶元素发现新人比自己高,让栈顶出栈并且计算栈顶元素和新人的距离。如此往复。在栈里面的人肯定都是比较高的,最终如果没有人了,栈里面的元素没有找到比自己高的,所以他们的距离就是0。
可以用下面这个图表示:
上面这个图已经很清楚了,不过最近dansen找到了一个做动画的软件manim,顺便用这个题目练练手,下面这个是视频动画。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& arr)
{
// 默认为0
vector<int> res(arr.size(), 0);
// 栈里面存放当前的索引位置,arr[st.top()]可以获得对应的数组值
stack<int> indexes;
for (int i = 0; i < arr.size(); ++i) {
// 如果当前元素大于栈顶元素,说明需要让栈顶出栈
while (!indexes.empty() && arr[i] > arr[indexes.top()]) {
auto index = indexes.top();
indexes.pop();
// 当前的索引位置-栈顶元素的索引位置
res[index] = i - index;
}
indexes.push(i);
}
return res;
}
};
单调栈里面的元素都是有序的,遇到新元素,发现不能保证有序,就会让之前的不能有序元素都出栈,直到有序。
这个特性对于某些场景很好用,性能复杂度,后面还有很多题目会继续深入讲解,然后也会使用图片和视频的方式,如果你觉得不错就点个赞吧,所有的资源(本题解、源码、图片drawio源码、视频manim源码)都会上传到咱公众号的Github基地,如果有问题欢迎提交PR,非常感谢你的观看。