代码随想录训练营二刷第六十一天 | 503.下一个更大元素II 42. 接雨水

代码随想录训练营二刷第六十一天 | 503.下一个更大元素II ● 42. 接雨水

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

题目链接：https://leetcode.cn/problems/next-greater-element-ii/
思路：循环数组多遍历一次，逻辑上拼一块往单调栈里放。

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[stack.peek()] < nums[i%len]) {
                res[stack.peek()] = nums[i%len];
                stack.pop();
            }
            stack.push(i%len);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、42. 接雨水

题目链接：https://leetcode.cn/problems/trapping-rain-water/
思路：接雨水得是凹槽处才能接，如2,1,3。1是凹槽，h是左右第一个高点中的最小者，w是右侧-左侧-1。如此栈内应放索引，应为自栈顶到栈底单调递减，当前元素小于栈顶加入，等于栈顶替换掉，大于栈顶就找到右边第一个最大值了。此时便可出栈计算。

class Solution {
   public int trap(int[] height) {
        Deque<Integer> stack = new LinkedList<>();
        int sum = 0;
        stack.push(0);
        for (int i = 1; i < height.length; i++) {
            if (height[i] < height[stack.peek()]) {
                stack.push(i);
            } else if (height[i] == height[stack.peek()]) {
                stack.pop();
                stack.push(i);
            } else {
                while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                    int mid = stack.pop();
                    if (!stack.isEmpty()) {
                        int h = Math.min(height[i], height[stack.peek()]) - height[mid];
                        int w = i - stack.peek() - 1;
                        sum += h * w;
                    }
                }
                stack.push(i);
            }
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26