代码随想录算法训练营第五九天 | 下一个更大元素II、接雨水

LeetCode 503.下一个更大元素II
LeetCode 42. 接雨水

下一个更大元素II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

• 问题的关键在于在遍历的过程中模拟走了两遍 nums

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);

        stack.push(0);
        int length = nums.length;
        for (int i = 0; i < length * 2; i++) {            
            while (!stack.isEmpty() && nums[i % length] > nums[stack.peek()]) {
                res[stack.peek()] = nums[i % length];
                stack.pop();
            }
            stack.push(i % length);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

接雨水

• 暴力
  • 也是使用双指针。
  • 按照列来计算的话，宽度一定是1了，我们再把每一列的雨水的高度求出来就可以了。
  • 只要记录左边柱子的最高高度 和 右边柱子的最高高度，就可以计算当前位置的雨水面积，这就是通过列来计算。
  • 当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度。 min(lHeight, rHeight) - height。
  • 只要从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积了。
  • 时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。 超时

class Solution {
    public int trap(int[] height) {
        // 暴力
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            // 第一个柱子和最后一个柱子不接水
            if(i == 0 || i == height.length - 1) continue;

            int rHeight = height[i]; // 记录右边柱子的最高高度
            int lHeight = height[i]; // 记录左边柱子的最高高度
            for (int r = i + 1; r < height.length; r++){
                rHeight = Math.max(rHeight, height[r]);
            }
            for (int l = i - 1; l >= 0; l--){
                lHeight = Math.max(lHeight, height[l]);
            }
            int h = Math.min(rHeight, lHeight) - height[i];
            if (h > 0) sum += h;
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 双指针优化

  • 优化思路是讲取左侧最高高度和右侧最高高度脱离出来，提前处理
  • 暴力解法中，为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。
  • 我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算。
  • 从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
  • 从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);

class Solution {
    public int trap(int[] height) {
        // 双指针优化
        if (height.length <= 2) return 0;
        int[] maxLeft = new int[height.length];
        int[] maxRight = new int[height.length];
        int length = height.length;

        // 记录每个柱子左边柱子的最大高度
        maxLeft[0] = height[0];
        for (int i = 1; i < length; i++) {
            maxLeft[i] = Math.max(height[i], maxLeft[i-1]);
        }

        // 记录每个柱子右边柱子的最大高度
        maxRight[length-1] = height[length-1];
        for (int i = length-2; i >= 0; i--) {
            maxRight[i] = Math.max(height[i], maxRight[i+1]);
        }

        // 求和
        int sum = 0;
        for (int i = 0; i < length; i++) {
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        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
27
28
29

• 单调栈
  • 单调栈就是保持栈内元素有序，需要自己维持顺序。
  • 通常是一维数组，要寻找任一个元素的右边或左边第一个比自己大或者小的元素的位置，此时用单调栈。

class Solution {
    public int trap(int[] height) {
        if (height.length <= 2) return 0;
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        int sum = 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 {
                // pop up all lower value
                while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                    int mid = stack.peek();
                    stack.pop();
                    if (!stack.isEmpty()) {
                        int h = Math.min(height[stack.peek()], height[i]) - height[mid];
                        int w = i - stack.peek() - 1;
                        int hold = h * w;
                        if (hold > 0) sum += hold;
                    }
                }
                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
27
28
29
30
31
32
33