单调栈

单调栈模板

int[] calculateGreaterElement(int[] nums) {
    int n = nums.length;
    // 存放答案的数组
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>(); 
    // 倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.isEmpty() && s.peek() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的更大元素
        res[i] = s.isEmpty() ? -1 : s.peek();
        s.push(nums[i]);
    }
    return res;
}

这就是单调队列解决问题的模板。for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素，所以他们不可能被作为后续进来的元素的下一个更大元素了。

分析它的时间复杂度，要从整体来看：总共有 n 个元素，每个元素都被 push 入栈了一次，而最多会被 pop 一次，没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的，也就是 O(n) 的复杂度。

LeetCode 496.下一个更大的元素Ⅰ

题目说 nums1 是 nums2 的子集，那么我们先把 nums2 中每个元素的下一个更大元素算出来存到一个映射里，然后再让 nums1 中的元素去查表即可

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 记录 nums2 中每个元素的下一个更大元素
        int[] greater = calculateGreaterElement(nums2);
        // 转化成映射：元素 x -> x 的下一个最大元素
        HashMap<Integer, Integer> greaterMap = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            greaterMap.put(nums2[i], greater[i]);
        }
        // nums1 是 nums2 的子集，所以根据 greaterMap 可以得到结果
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = greaterMap.get(nums1[i]);
        }
        return res;
    }

    int[] calculateGreaterElement(int[] nums) {
        // 见上文
    }
}

LeetCode 739.每日温度

这个问题本质上也是找下一个更大元素，只不过现在不是问你下一个更大元素的值是多少，而是问你当前元素距离下一个更大元素的索引距离而已。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        // 这里放元素索引，而不是元素
        Stack<Integer> s = new Stack<>(); 
        // 单调栈模板
        for (int i = n - 1; i >= 0; i--) {
            while (!s.isEmpty() && temperatures[s.peek()] <= temperatures[i]) {
                s.pop();
            }
            // 得到索引间距
            res[i] = s.isEmpty() ? 0 : (s.peek() - i); 
            // 将索引入栈，而不是元素
            s.push(i); 
        }
        return res;
    }
}

LeetCode 503.下一个更大的元素Ⅱ

这个问题肯定还是要用单调栈的解题模板，但难点在于，比如输入是 [2,1,2,4,3]，对于最后一个元素 3，如何找到元素 4 作为下一个更大元素。

对于这种需求，常用套路就是将数组长度翻倍：

这样，元素 3 就可以找到元素 4 作为下一个更大元素了，而且其他的元素都可以被正确地计算。

有了思路，最简单的实现方式当然可以把这个双倍长度的数组构造出来，然后套用算法模板。但是，我们可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();
        // 数组长度加倍模拟环形数组
        for (int i = 2 * n - 1; i >= 0; i--) {
            // 索引 i 要求模，其他的和模板一样
            while (!s.isEmpty() && s.peek() <= nums[i % n]) {
                s.pop();
            }
            res[i % n] = s.isEmpty() ? -1 : s.peek();
            s.push(nums[i % n]);
        }
        return res;
    }
}

LeetCode 1019.链表中的下一个更大节点

这道题输入的是一条单链表，我们把它转化成数组，方便用索引访问即可直接套用
单调栈模板 中的 nextGreaterElement 函数逻辑。

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        // 把单链表转化成数组，方便通过索引访问
        ArrayList<Integer> nums = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) {
            nums.add(p.val);
        }
        // 存放答案的数组
        int[] res = new int[nums.size()];
        Stack<Integer> stk = new Stack<>();
        // 单调栈模板，求下一个更大元素，从后往前遍历
        for (int i = nums.size() - 1; i >= 0; i--) {
            while (!stk.isEmpty() && stk.peek() <= nums.get(i)) {
                stk.pop();
            }
            // 本题要求没有下一个更大元素时返回 0
            res[i] = stk.isEmpty() ? 0 : stk.peek();
            stk.push(nums.get(i));
        }
        return res;
    }
}

LeetCode 1944.队列中可以看到的人数

这道题显然要用到
单调栈技巧：靠左的高个子可以把靠右相邻的矮个子都「挤掉」，相当于计算下一个更大元素，即
单调栈的几种模板实现 中的 nextGreaterElement 函数。

只不过这道题不是问你下一个更大元素是多少，而是问你当前元素和下一个更大元素之间的元素个数。

class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] res = new int[n];
        // int[] 记录 {身高，小于等于该身高的人数} 二元组
        Stack<Integer> stk = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            // 记录右侧比自己矮的人
            int count = 0;
            // 单调栈模板，计算下一个更大或相等元素（身高）
            while (!stk.isEmpty() && heights[i] > stk.peek()) {
                stk.pop();
                count++;
            }
            // 不仅可以看到比自己矮的人，如果后面存在更高的的人，也可以看到这个高人
            res[i] = stk.isEmpty() ? count : count + 1;
            stk.push(heights[i]);
        }
        return res;
    }
}

LeetCode 1475.商品折扣后的最终价格

这道题就用到了
单调栈的几种模板实现 中讲到的一个单调栈模板：计算下一个更小或相等的元素。

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] res = new int[n];
        // 下一个小于等于 price[i] 的价格就是优惠券折扣
        int[] nextElement = nextLessOrEqualElement(prices);
        for (int i = 0; i < prices.length; i++) {
            // 如果存在优惠券，则减少相应的价格
            if (nextElement[i] != -1) {
                res[i] = prices[i] - nextElement[i];
            } else {
                res[i] = prices[i];
            }
        }
        return res;
    }

    // 单调栈模板：计算 nums 中每个元素的下一个更小或相等的元素
    int[] nextLessOrEqualElement(int[] nums) {
        int n = nums.length;
        // 存放答案的数组
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();
        // 倒着往栈里放
        for (int i = n - 1; i >= 0; i--) {
            // 删掉 nums[i] 后面较大的元素
            while (!s.isEmpty() && s.peek() > nums[i]) {
                s.pop();
            }
            // 现在栈顶就是 nums[i] 身后的更小或相等元素
            res[i] = s.isEmpty() ? -1 : s.peek();
            s.push(nums[i]);
        }
        return res;
    }
}