LeetCode：单调栈

基础

本板块整理自灵茶山艾府b站视频单调栈【基础算法精讲 26】_哔哩哔哩_bilibili

通过一道例题进行讲解：

题目传送门：[739.

每日温度 - 力扣（LeetCode）](https://leetcode.cn/problems/daily-temperatures/)

朴素算法就是，我们直接考虑对于每个元素遍历，找到他右边第一个比他大的数，但是这样明显是一个 $O(n^2)$ 复杂度的算法，如何优化呢？

首先不难想到的是我们倒着进行遍历，如果我们的温度序列是 $1,6,3,5,5,2,1,6$ ,并且我们已经遍历完了最后的4个数,那么我们不难推出，再后续的遍历中比当前值大的数不可能是2，1（因为前面有一个5更大）。

总结一下当前情况是，由于5的出现，右侧2，1一定不会成为左侧某个数下一个更大的数了。所以再后续的遍历中我们就可以把这两个数去掉，不去遍历他们两个了。

以上就是单调栈算法的核心思想了

下面介绍两种常见的单调栈写法：

从右到左（将下一个最大数存入栈中）

此时维护的栈是一个顶小底大的栈：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> st; 
        for(int i=n-1;i>=0;--i){
            int t = temperatures[i];
            while (!st.empty()&&t >= temperatures[st.top()]) st.pop();
            if (!st.empty()) {
                ans[i] = st.top() - i;
            }
            st.push(i);
        }
        return ans;
    }
};

从左到右（将还没有找到下一个最大的数存入栈中）

此时维护的栈仍是一个顶小底大的栈：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> st;
        for(int i=0;i<n;++i){
            int t = temperatures[i];
            while (!st.empty() && t > temperatures[st.top()]) {
                ans[st.top()] = i-st.top(); st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};

单调栈题单

单调栈

每日温度（单调栈模板题）
商品折扣后的最终价格
下一个更大元素 I
下一个更大元素 II
链表中的下一个更大节点 1571
股票价格跨度 1709
表现良好的最长时间段 1908
132 模式 ~2000
美丽塔 II 2072
下一个更大元素 IV 2175
使数组按非递减顺序排列 2482
每个元素为最大值的最大范围（会员题）

矩形系列

柱状图中最大的矩形
最大矩形
统计全 1 子矩形 1845

字典序最小

去除重复字母
扩展：重复个数不超过 limit
移掉 K 位数字 ~1800
找出最具竞争力的子序列 1802
拼接最大数

贡献法（计算所有子数组的……的和）

子数组的最小值之和 1976
子数组范围和（最大值-最小值） O(n)\mathcal{O}(n)O(n) 做法 ~2000
子数组最小乘积的最大值 2051
操作使得分最大 2397
巫师的总力量和（最小值*和） 2621