单调栈的使用

本是古典何须时尚 2024-04-05 07:16 61阅读 0赞

#### 一、介绍 ####

单调栈，顾名思义就是栈内元素是有单调性的栈，单调栈在入栈的时候，需要将待入栈的元素和栈顶元素进行对比，看待加入栈的元素入栈后是否会破坏栈的单调性，如果不会，直接入栈；否则一直弹出到满足条件为止。

单调栈何时用：为任意一个元素找左边和右边第一个比自己大/小的位置可以使用单调栈.

由于每个元素最多各自进出栈一次,复杂度是O(n).

#### 二、单调栈的模板 ####

stack<int> st;
    //此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
    for (遍历这个数组){
        if (栈空 || 栈顶元素大于等于当前比较元素){
            入栈;
        }else{
            while (栈不为空 && 栈顶元素小于当前元素){
                栈顶元素出栈;
                更新结果;
            }
            入栈;
        }
    }
    
    或者简化为:
    //此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
    for (遍历这个数组){
        while (栈不为空 && 栈顶元素小于当前元素){  //这里栈为单调不减
            栈顶元素出栈;
            更新结果;
        }
        入栈;
    }

#### 三、实例 ####

![243efa80eff348d7ae646c10029677a6.png][]

分析：

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& temperatures) {
            int length = temperatures.size();
            vector<int> res(length, 0);
            stack<int> stackTemp;
            for (int i = 0; i < temperatures.size(); ++i) {
                // 栈不为null，当前的值大于栈顶
                while (!stackTemp.empty() && temperatures[i] > temperatures[stackTemp.top()]) {
                    auto index = stackTemp.top(); // 获取栈顶
                    stackTemp.pop();
                    res[index] = i - index; // 计算索引
                }
                stackTemp.push(i);
            }
            return res;
        }
    };

参考：

[\[数据结构\]——单调栈\_lucky52529的博客-CSDN博客\_什么是单调栈][lucky52529_-CSDN]

[单调栈简介\_未闻名的博客-CSDN博客][-CSDN]

[力扣][Link 1]

[243efa80eff348d7ae646c10029677a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/707d1ec7efa64ace9fbf160a2e89c02f.png
[lucky52529_-CSDN]: https://blog.csdn.net/lucky52529/article/details/89155694
[-CSDN]: https://blog.csdn.net/qq_41296917/article/details/123339708
[Link 1]: https://leetcode.cn/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode-solution/