单调栈入门+动画视频

对于栈这种数据结构，相信大部分同学都会觉得很简单，它只有一个特性，那就是先进后出。

本篇我们来看一个特殊的栈结构，也就是单调栈。单调栈顾名思义，就是栈里面的数据是有序的，比如栈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，顺便用这个题目练练手，下面这个是视频动画。

C++源码

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，非常感谢你的观看。