monotone stack

单调栈

单调栈中存放的数据是有序的，按照从栈底到栈顶的顺序可分为(从栈顶往栈底方向看)：

• 单调递增栈：由栈底到栈顶的数据按由大到小
• 单调递减栈：由栈底到栈顶的数据按由小到大

性质

• 单调递增栈：可以找到当前遍历的数左起第一个更小元素，或是找到数组中元素右边第一个更大元素
• 单调递减栈：找到当前遍历的数左边第一个更大元素.

举例说明：假设数组num = [2, 1, 4, 6, 5]

• 找到数组中每个元素右边第一个比它本身大的元素，没找到则赋值0
  • 创建一个单调递增栈stack<int> stk，结果数组res[num.size()]并初始化为0
  • 将num[0] = 2入栈，此时栈为:[0](将索引入栈，左为栈底，右为栈顶)
  • num[1] = 1比栈顶元素小，入栈，此时栈为:[0，1]
  • num[2] = 4比栈顶元素大，出栈，res[1] = num[2],出栈，此时栈为:[0]
  • num[2] = 4比栈顶元素大，出栈，res[0] = num[2],出栈，此时栈为:[]；栈为空，将当前元素入栈，此时栈为[2]
  • num[3] = 6比栈顶元素大，出栈，res[2] = num[3],出栈，此时栈为:[]；栈为空，将当前元素入栈，此时栈为[3]
  • num[4] = 5比栈顶元素小，入栈，此时栈为:[3，4].
  • 返回结果res = [4, 4, 6, 0, 0]
• 找到每个元素左边第一个比它本身大的元素，没有找到则赋值0
  • 创建一个单调递减栈stack<int> stk，结果数组res[num.size()]并初始化为0
  • 将num[0] = 2入栈，此时栈为:[0](将索引入栈，左为栈底，右为栈顶)
  • num[1] = 1比栈顶元素小，出栈，res[1] = num[0]此时栈为:[]；栈为空，将当前元素入栈，此时栈为[1]
  • num[2] = 4比栈顶元素大，入栈，此时栈为:[1, 2]
  • num[3] = 6比栈顶元素大，入栈，此时栈为:[1, 2, 3]
  • num[4] = 5比栈顶元素小，出栈，res[4] = num[3]
  • num[4] = 5比栈顶元素大，入栈，此时栈为:[1, 2, 4].
  • 返回结果res = [0, 2, 0, 0, 6]

力扣相关题目

• 题目链接1：503. 下一个更大元素 II

给定一个循环数组nums（nums[nums.length - 1]的下一个元素是nums[0]），返回nums中每个元素的 下一个更大元素 。

数字x的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出-1。

示例1：

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

示例2：

输入： nums = [1,2,3,4,3]
输出： [2,3,4,-1,4]

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

• 题目链接2：739. 每日温度

给定一个整数数组temperatures ，表示每天的温度，返回一个数组answer，其中answer[i]是指在第i天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用0来代替。

示例1：

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

示例2：

输入： temperatures = [30,40,50,60]
输出： [1,1,1,0]

示例3：

输入： temperatures = [30,60,90]
输出： [1,1,0]

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