力扣labuladong一刷day50天单调栈

文章目录

总结

单调栈就这一类特殊题目，一个扳手对应一个螺丝，把模板给记牢了即可。

一、496. 下一个更大元素 I

题目链接：https://leetcode.cn/problems/next-greater-element-i/
思路：一般求下一个更大元素或者更小元素基本都是使用单调栈，而单调栈就是维护一个有序的栈，求下一个更大元素，栈内放的就是自栈底到栈顶单调递增，构造过程就是，只要新元素大于栈顶元素，那么就找到了离栈顶元素最近的一个大于他的元素，栈顶就可以出栈了，之后把新元素入栈。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2){
        Deque<Integer> stack = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
                map.put(stack.peek(), nums2[i]);
                stack.pop();
            }
            stack.push(nums2[i]);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}

二、739. 每日温度

题目链接：https://leetcode.cn/problems/daily-temperatures/
思路：
本题和上一题类似，但本题是最简单的单调栈应用，十分明确，就是求右边第一个比他大的元素，然后就是套模板。

class Solution {
   public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[temperatures.length];
        for (int i = 0; i < res.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > stack.peek()) {
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }
}

三、503. 下一个更大元素 II

题目链接：https://leetcode.cn/problems/next-greater-element-ii/
思路：一般这种循环数组都是有套路的，最常见的处理手段是把遍历长度虚拟扩展两倍，然后对数组长度取余，到原数组中去取数。另外就是Deque stack = new LinkedList<>();比Stack要快很多。用栈的话尽量用这个。

class Solution {
  public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        int len = nums.length;
        int[] res = new int[len];
        Arrays.fill(res, -1);
        for (int i = 0; i < len * 2; i++) {
            while (!stack.isEmpty() && nums[i%len] > nums[stack.peek()]) {
                res[stack.peek()] = nums[i%len];
                stack.pop();
            }
            stack.push(i%len);
        }
        return res;
    }
}