03 单调栈

单调栈通过维持栈内值的单调递增（递减）性，在整体 O(n) 的时间内处理需要大小比较的问题。

739 每日温度 (opens new window)

给定每天的温度，求对于每一天需要等几天才可以等到更暖和的一天。如果该天之后不存在更暖和的天气，则记为 0。

输入是一个一维整数数组，输出是同样长度的整数数组，表示对于每天需要等待多少天。

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

解析：

​ 本题可以通过维持一个单调递减的栈，表示每天的温度；而本题要求的是当前温度到更高温度的天数差，所以栈中的元素表示的是温度对应的日期，即温度在数组中的位置。单调递减的栈，所以栈顶表示的是栈内最低温度的日期。

​ 从左向右遍历数组，对于日期 p ，如果 p 对应的温度高于栈顶的日期 q 对应的温度，则遇到了更暖和的一天，将 q 出栈并记录天数差为 p - q；如果 p 对应的温度低于栈顶的日期 q 对应的温度，或者栈为空，则将 p 压入栈中，然后继续考虑下一天的情况。

​ 遍历完数组之后，栈内剩余的日期对应的温度都是递减的，说明他们之后不存在更暖和的天气。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> s;
        int len = temperatures.size();
        vector<int> ans(len);
        for(int i=0;i<len;++i){
            // 出栈栈内低于当前日期温度的日期，并计算天数差
            while(!s.empty()){
                int preTemp = temperatures[s.top()];
                // 如果栈顶日期温度大于当前日期温度，停止出栈
                if(preTemp >= temperatures[i]){
                    break;
                }
                ans[s.top()] = i - s.top();
                s.pop();
            }
            s.push(i);
        }
        // 遍历完成之后，还未出栈的日期之后没有更高的温度
        while(!s.empty()){
            ans[s.top()] = 0;
            s.pop();
        }
        return ans;
    }
};

503 下一个更大元素 II (opens new window)

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。如果不存在，则输出 -1。

输入是一个一维整数数组，输出是同样长度的整数数组，表示对于原数组每位置的数下一个更大元素。

输入: [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

解析：

​ 和每日温度相似，本题也可以通过维持一个单调递减的栈，表示原数组元素位置。

​ 本题和739 每日温度 (opens new window)的区别在于本题待遍历的数组是一个循环数组，遍历循环数组的常用方式是将这个循环的圈拉直，即复制该序列的前 n-1 个元素拼接在原序列的后面。即用一个原数组的拷贝与其自身拼接成一个数组，例如将ABCDEF循环数组拉直有ABCDEFABCDEF，就有了A到A、B倒B……F到F的循环。

​ 更简单可以避免增加空间开销，直接可以用模运算遍历数组，例如长度为 n 的循环数组元素表示为array[i%n]

​ 按照上述循环数组遍历方法，从左向右遍历，对于当前位置 p，如果 p 对应的元素值大于单调栈栈顶 q 对应的元素值，则 q 遇到的更大值，在 q 位置保留 p 对应的值。如果栈为空，或者p 对应的元素值小于单调栈栈顶 q 对应的元素值，则将 p 压入栈，然后考虑下一个元素。

​ 遍历完数组之后，栈内剩余的位置对应的元素值都是递减的，说明他们之后不存在更大的元素。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> s;
        int len = nums.size();
        // ans都初始化成 -1 就不用再去考虑没有出栈的元素了
        vector<int> ans(len,-1);
        for(int i=0;i<2*len-1;++i){
            while(!s.empty()){
                int preVal = nums[s.top()%len];
                if(preVal >= nums[i%len]){
                    break;
                }
                ans[s.top()%len] = nums[i%len];
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

42 接雨水 (opens new window)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

解析:

84 柱状图中最大的矩形 (opens new window)

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

解析:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int n = heights.size();
        vector<int> left(n), right(n);
        for(int i=0;i<n;++i){
            while(!st.empty() && heights[st.top()] >= heights[i]){
                st.pop();
            }
            left[i] = st.empty()?-1:st.top(); // -1 作为哨兵
            st.push(i);
        }

        st = stack<int>();
        for(int i=n-1;i>=0;--i){
            while(!st.empty() && heights[st.top()] >= heights[i]){
                st.pop();
            }
            right[i] = st.empty()?n:st.top(); // n 作为哨兵
            st.push(i);
        }

        int ans = 0;
        for(int i=0;i<n;++i){
            ans = max(ans,(right[i]-left[i]-1)*heights[i]); // 面积=宽X高
        }
        return ans;
    }
};

85 最大矩形 (opens new window)

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

解析:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        if(m==0 || n==0){
            return 0;
        }
        
        vector<vector<int>> left(m,vector<int>(n,0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
                }
            }
        }

        int ans = 0;
        for(int j=0;j<n;++j){
            stack<int> st;
            vector<int> up(m), down(m);
            for(int i=0;i<m;++i){
                while(!st.empty() && left[st.top()][j] >= left[i][j]){
                    st.pop();
                }
                up[i] = st.empty()?-1:st.top();
                st.push(i);
            }

            st = stack<int>();
            for(int i=m-1;i>=0;--i){
                while(!st.empty() && left[st.top()][j] >= left[i][j]){
                    st.pop();
                }
                down[i] = st.empty()?m:st.top();
                st.push(i);
            }

            for(int i=0;i<m;++i){
                int height = down[i] - up[i] - 1;
                ans = max(ans,height*left[i][j]);
            }
        }

        return ans;
    }
};