什么是单调栈？

单调栈是一种特殊的栈，其主要特性是栈内的元素始终保持某种单调性，通常用于优化解决需要重复遍历的问题，例如找出数组中某个元素的 下一个更大元素 或 下一个更小元素。

根据栈内元素的单调性，单调栈可以分为两类：

1. 单调递增栈：栈内元素从栈底到栈顶递增。

2. 单调递减栈：栈内元素从栈底到栈顶递减。

参考：单调栈 - OI Wiki

单调栈的特点

• 操作规则：

  • 如果当前元素破坏了栈的单调性（即比栈顶元素小或大，取决于栈的类型），就不断弹出栈顶元素，直到恢复单调性。

  • 新元素可以入栈，保持栈的单调性。

• 作用：

  • 常用于找到 左侧最近的比某元素大（或小） 的值或 右侧最近的比某元素大（或小） 的值。

  • 时间复杂度为 O(n)，因为每个元素最多入栈和出栈一次。

示例：下一个更大的元素问题

题目

[739. 每日温度](https://leetcode.cn/problems/daily-temperatures/)

给定一个数组，找到每个元素右侧第一个比它大的元素。如果不存在，返回 -1。

示例输入：

nums = [73,74,75,71,69,72,76,73]

示例输出：

[1,1,4,2,1,1,0,0]

思路

首先想到的当然是暴力解法，两层for循环，把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)

遇到如下的情况可以考虑使用单调栈：

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。

如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

使用单调栈主要有三个判断条件。

• 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况

• 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况

• 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

使用单调栈求解

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st; // 递增栈
        vector<int> result(T.size(), 0);
        for (int i = 0; i < T.size(); i++) {
            while (!st.empty() && T[i] > T[st.top()]) { // 注意栈不能为空
                result[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);

        }
        return result;
    }
};

类似题目

496. 下一个更大元素 I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        unordered_map<int, int> umap;
        for (int i = 0; i < nums2.size(); i++) {
            while (!st.empty() && st.top() < nums2[i]) {
                umap.insert({st.top(), nums2[i]});
                st.pop();
            }
            st.push(nums2[i]);
        }
        for (int i = 0; i < nums1.size(); i++) {
            if (umap.contains(nums1[i]))
                result[i] = index_map[nums1[i]];
            else
                result[i] = -1;
        }
        return result;
    }
};

503. 下一个更大元素 II

此题目是成环的数组：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        stack<int> st;
        for (int i = 0; i < 2 * nums.size(); i++) {
            while (!st.empty() && nums[st.top() % nums.size()] < nums[i % nums.size()]) {
                if (st.top() < nums.size())
                    result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i);
        }
        return result;
    }
};

// 版本二
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;
        stack<int> st;
        for (int i = 0; i < nums.size() * 2; i++) {
            // 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
            while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }
        return result;
    }
};