单调栈

简介

单调栈实际上也是栈，但他利用了一些巧妙的逻辑，让每次新元素入栈后，栈内元素都保持 有序（单调递增或单调递减），那么，这个逻辑是什么，其实很简单，以栈底-栈顶单调递增 为例，每次新元素入栈时，让栈内元素与新元素判断，比新元素大的栈内元素出栈即可。

用途

单调栈的用途并不广泛，只处理一种典型问题，Next Greater Element

单调栈模板

下面举一个例子说明其模板，现有这样一道题：给你一个数组nums，请你返回一个等长的结 果数组，结果数组中对应索引储存着下一个更大元素，如果没有更大的元素，就存-1，例如 输入数组 nums = [2,1,2,4,3],返回数组[4,2,4,-1,-1] 解释：第一个2后面比2大的数是4，第二个2后面比2大的数是4，4后面没有比4大的数，填 -1，3后面没有比3大的数，填-1.

• 暴力解法：对每个元素的后面进行扫描，找到第一个更大的元素就可以了，时间复杂度为 O（n^2）
• 单调栈法：把数组元素想象成并列的数，元素大小想象成树的高度，在某个位置时，后面 可见的第一颗树就是它的 Next Greater Number.
  • 实现代码(C++)：

  vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        s.push(nums[i]);
    }
    return res;}

这就是单调栈解决问题的模板，倒着入栈其实就是正着出栈，while循环是排除两颗高树间 的矮树，这个算法的复杂度只有O（n），尽管它存在for循环嵌套while循环，但要分析一个 算法的时间复杂度，要从整体入手，总共有n个元素，每个元素都被push入栈一次，最多被 pop一次，没有对于操作，计算规模与元素规模还是成正比的，也就是O（n）复杂度

单调栈模板改良处理环形数组

同求next Greater Number 如果要求环形数组，怎么办 比如输入一个数组[2,1,2,4,3].返回数组[4,2,4,-1,4]拥有了环形属性，最后一个元素3绕 了一圈后找到了比自己大的元素4. 这种情况一般都是通过%运算符求模(余数)，来获得环形特效 对于这个问题还是要用单调栈解题模板，对环形需求，常用套路是将数组长度翻倍，我们也 可以不构造新数组，而是用循环数组来模拟数组长度翻倍的效果 示例代码（C++）：

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);
    stack<int> s;
    // 假装这个数组长度翻倍了
    for (int i = 2 * n - 1; i >= 0; i--) {
        // 索引要求模，其他的和模板一样
        while (!s.empty() && s.top() <= nums[i % n]) {
            s.pop();
        }
        res[i % n] = s.empty() ? -1 : s.top();
        s.push(nums[i % n]);
    }
    return res;
}

参考博客：labuladong的算法小抄-单调栈结构解决三道算法题