栈有着广泛的应用，比如逆波兰表达式，表达式求值，迷宫问题求解，程序调用等，不过这些问题今天都不涉及哈哈哈哈。关于程序执行期间，各个函数的相互调用使用的调用栈，可以参考这里。

单调栈属于栈的具体应用，而非栈这种数据结构的简单使用。此类问题一般用于求解以下场景：序列中某个元素的下一个最大元素，元素间的最大跨度，维持某一状态持续的最长时间等。以序列 [2,1,3,4] 为例，1 的下一个最大元素就是 3，而不是 4；最大上升的跨度为从 2 到 4，跨越了 2 个数。对于这种问题都可以用单调栈求解。

栈

也许在上数据结构这门课的时候，经常遇到一个问题，一个栈压入一个序列，随缘pop，判断哪个是合理的pop，哪个是不合理的pop，之前都是脑内演算。很巧的今天我在刷题期间也遇到了，记录一下如何用代码判断pop序列是否合理。

题目

Given a stack which can keep $M$ numbers at most. Push $N$ numbers in the order of 1, 2, 3, …, $N$ and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack.

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): $M$ (the maximum capacity of the stack), $N$ (the length of push sequence), and $K$ (the number of pop sequences to be checked). Then $K$ lines follow, each contains a pop sequence of $N$ numbers. All the numbers in a line are separated by a space.

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

示例输入

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

示例输出

YES
NO
NO
YES
NO

众所周知，栈是先进先出的一种数据结构，进栈为push，出栈为pop。题目的大概意思就是给定栈的最大空间，压入的序列和待检查的pop序列，因为栈是随缘pop的，判断哪个pop序列是正确的，哪个pop序列是错误的。

脑内演算

对于序列 1, 2, 3, 4, 5, 6, 7，很容易得到栈是如何工作的，即压入一个元素立刻弹出即可。push 1，pop 1，push 2，pop 2，一直到push 7，pop 7。
对于序列 5, 6, 4, 3, 7, 2, 1，也可以得到栈的工作顺序为：push 1, 2, 3, 4, 5，而后pop 5，而后push 6 pop 6，pop 4，pop 3，push 7 pop 7，pop 2，pop 1。
对于序列 3, 2, 1, 7, 5, 6, 4，如果pop 7后，后面的顺序必然是 6，5，4而不可能是5，6，4。因此这个序列是错误的。
对于序列 7, 6, 5, 4, 3, 2, 1，在栈空间为5的情况下，不可能第一次就pop 7，因此这个序列是错误的。

一般化

在脑内演算后，也很容易发现题的难点在于不确定性的pop，可能在第一次pop，也可能在第三次pop，且每次pop几个元素也是不确定的。

我们实现知道了元素的进栈顺序，是1，2，3，4，…，$N$这样的顺序序列，所以，如果想办法按着它给出的序列模拟压栈和弹栈，如果能模拟出来，说明序列正确，模拟不出来说明序列错误。

第一步，创建一个序列，读取题目示例输入的序列：
1
2
for (int i = 1; i <= n; i++)
scanf("%d", &arr[i]);
第二步，创建一个栈，并按元素的输入顺序组织元素进栈，开始按读取序列元素的顺序进行压栈和弹栈。
对输入序列设立标志位，并初始化标志位为1。当刚进栈的元素和输入序列标志位的元素相等时，说明此时元素要弹栈，则执行弹栈操作，且标志位自增向后移动；若不相等，则继续组织进栈，直到进栈元素和输入序列中标志位的元素相等。若一直不相等，则表明此序列错误。因此核心算法程序如下：

#include <iostream>
#include <stack>

using namespace std;

int arr[1002];

int main(int argc, char const *argv[])
{
    int m, n, k;
    cin >> m >> n >> k;
    for (int j = 0; j < k; j++)
    {
        for (int i = 1; i <= n; i++)
            scanf("%d", &arr[i]);
        int flag = 0, pos = 1;
        stack <int> s;
        for (int i = 1; i <= n; i++)
        {
            s.push(i);
            if (s.size() > m) break;
            while (!s.empty() && s.top() == arr[pos])
            {
                s.pop();
                pos += 1;
            }
        }
        if (pos == n + 1) flag = 1;
        if (flag == 1) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

单调栈

同样以 [2,1,3,4] 为例，假设此时我们有一个容器，输入一个数，容器顶部的元素是下一个最大的数。对于 1 而言，后面的最大元素是 3，因此可以得到一个结论：3 比 1 先进入容器，更通用一些：如果判断下一个最大元素，序列就要倒序进入容器，如果判断上一个最大元素，序列就要顺序进入容器。

由于 1 比 2 先进入容器，但 2 的下一个最大元素是 3 而不是 1，那么就需要在容器中进行一些操作来删除 1。即 1 比 2 早进入容器，却要先从容器种出来，那么有什么容器是后入先出的呢？当然是栈。这也就是单调栈的由来。我们总结一下：

如果是求下一个最大元素，就需要倒序遍历序列，否则正序遍历；
判断输入的元素和栈顶元素的关系，如果是求最大元素，那么就需要弹出栈顶所有的小元素；

不过还有一些小细节，这个就来看具体的题目了。

下一个最大/小元素

496. 下一个更大元素 I

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是 -1 。返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的下一个更大元素。示例：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

根据前面的结论，写出程序并分析：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> stk;
        unordered_map<int, int> m1;
        vector<int> res(10005, -1);
        // 求下一个最大元素，因此要倒序进入
        for (int i = nums2.size() - 1; i >= 0; i--) {
            // 弹出栈顶的小元素
            while (!stk.empty() && nums2[i] >= stk.top()) {
                stk.pop();
            }
            // 栈为空，说明没有比当前元素更大的，只能 -1
            // 否则栈顶比输入大
            res[nums2[i]] = stk.empty() ? -1 : stk.top();
            // 并把当前元素放入栈中，用去后面序列元素的判断
            stk.push(nums2[i]);
        }
        vector<int> ans;
        for (auto i : nums1) {
            ans.push_back(res[i]);
        }
        return ans;
    }
};

739. 每日温度

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

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

和上一题不一样的是，这个题不在求下一个最大温度了，而是下一个最大温度的索引。因此压入栈中的是索引而不是温度，索引之间的差，就是相差的天数。在判断输入元素和栈顶元素的大小关系时，根据索引访问温度即可。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> stk;
        vector<int> res(n, 0);
        // 倒序输入
        for (int i = n - 1; i >= 0; i--) {
            // 抛弃掉温度低的，索引访问温度
            while (!stk.empty() && temperatures[i] >= temperatures[stk.top()]) {
                stk.pop();
            }
            // 如果今天温度不是最高的，那么索引的差距就是间隔的天数
            res[i] = stk.empty() ? 0 : stk.top() - i;
            // 把今天放进去
            stk.push(i);
        }
        return res;
    }
};

901. 股票价格跨度

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

这个题问的是：序列中小于等于当前元素，因此需要正序输入，确切来说，只能正序输入。此外，next() 方法会不断的调用，如果每次调用都通过输入来重新构建栈，就会超时。因此，我们把单调栈的核心算法封装进 next() 方法即可，且由于求的是时间跨度，因此压入栈中的是索引。个人认为，能独立把这个题写出来，单调栈就可以了。

class StockSpanner {
public:
    vector<int> arr;
    int n = 0;
    stack<int> stk;
    vector<int> tmp;
    StockSpanner() {

    }
    
    int next(int price) {
        // 序列元素
        arr.push_back(price);
        int res = build(price);
        return res;
    }

    int build(int price) {
        int a;
        // 保留大栈顶，如 100 60 80 则保留为 100 80
        while (!stk.empty() && price >= arr[stk.top()]) {
            stk.pop();
        }
        // 第一天，一定为 1
        if (n == 0)
            a = 1;
        // 否则，如果栈空了，说明前几天都比今天低，就返回天数。否则就求时间跨度
        else
            a = stk.empty() ? n + 1 : n - stk.top();
        // 把今天压入，这里先 +1 或先压入都可以，细节自行处理
        stk.push(n);
        n += 1;
        return a;
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

最大跨度问题

除了可以求解下一个最大元素外，单调栈还能求满足某一条件的最大跨度。

962. 最大宽度坡

给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。找出 A 中的坡的最大宽度，如果不存在，返回 0 。

示例 1：

输入：[6,0,8,2,1,5]
输出：4
解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.

是不是觉得毫无头绪，我刚开始也是这么想的，后来直到看了一个不错的题解。暴力破解能得到答案，但显然会超时，单调栈是如何应用到求最大跨度问题中呢？

首先来一点点的分析，由于要求解最大跨度，因此存储的肯定为索引。在者，对于 [9,8,1,0,1,9,4,0,4,1] 而言的最大跨度，我们希望在左边找很小的值，在右边找比左边大的值。并且有两个 0，显然第一个 0 能贡献的跨度更大。因此，基于以上两点，我们可以使用栈来存储单调递减序列的而索引，即：[9,8,1,0]，对应的索引是 [0,1,2,3]。如此，满足了找左侧很小值的目标，也满足了不考虑后面的 0。

之后，我们只要倒序遍历序列，依次和栈顶元素比较大小，如果大于，那么记录跨度并弹栈。随着弹栈的进行，索引会越来越小，也求到了更大的跨度。具体理解一下：

输入：[9,8,1,0,1,9,4,0,4,1]
单调递减元素:[9,8,1,0], 对应下标:[0,1,2,3], 严格单调递减栈s:[0,1,2,3]
j=9, nums[j]=1 > nums[s.top()]=nums[3]=0, pos=s.top()=3, pop出3, res=max(res, j-pos)=(0, 9-3)=6
     nums[j]=1 = nums[s.top()]=nums[2]=1, pos=s.top()=2, pop出2, res=max(res, j-pos)=(6, 9-2)=7
     nums[j]=1 < nums[s.top()]=nums[1]=8, 遍历下一个j
j=8, nums[j]=4 < nums[s.top()]=nums[1]=8, 遍历下一个j
     ... 
     ...
     ...

不难写出程序：

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        stack<int> stk;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (stk.empty() || nums[stk.top()] > nums[i]) {
                stk.push(i);
            }
        }
        int res = -1;
        for (int j = n - 1; j >= 0; j--) {
            while (stk.size() && nums[j] >= nums[stk.top()]) {
                res = max(res, j - stk.top());
                stk.pop();
            }
        }
        return res;
    }
};

维持某一状态最长的持续时间

这个题需要用到一些其他知识，因此和前缀和数组整理到一起了，可以观看下一篇博客。

Just for Life.

算法系列：单调栈

栈

题目