程序员社区

LeetCode-42-接雨水(Trapping Rain Water)

42. 接雨水

难度困难2330收藏分享切换为英文接收动态反馈

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

LeetCode-42-接雨水(Trapping Rain Water)插图
img
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

提示:

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

  1. Trapping Rain Water

Hard

11086166Add to ListShare

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

LeetCode-42-接雨水(Trapping Rain Water)插图1
img
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

LeetCode-42-接雨水(Trapping Rain Water)插图2
image-20210508090145236
LeetCode-42-接雨水(Trapping Rain Water)插图3
image-20210508092215460
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;

        int lastIdx = height.length - 2;
        int[] leftMaxes = new int[height.length];
        for (int i = 1; i <= lastIdx; i++) {
            leftMaxes[i] = Math.max(leftMaxes[i - 1], height[i - 1]);
        }

        int[] rightMaxes = new int[height.length];
        for (int i = lastIdx; i >= 1; i--) {
            rightMaxes[i] = Math.max(rightMaxes[i + 1], height[i + 1]);
        }

        // 遍历每一根柱子,看看每一根柱子上能放多少水
        int water = 0;
        for (int i = 1; i <= lastIdx; i++) {
            // 求出左边最大、右边最大中的较小者
            int min = Math.min(leftMaxes[i], rightMaxes[i]);
            // 说明这根柱子不能放水
            if (min <= height[i]) continue;
            // 说明这根柱子能放水
            water += min - height[i];
        }

        return water;
    }
}
LeetCode-42-接雨水(Trapping Rain Water)插图4
image-20210508092253898

优化1 ,减少一次遍历,求water的遍历的过程中,记录左侧的最大值

class Solution {
     public int trap(int[] height) {
        if (height == null || height.length <3 ) return 0;

        int lastIdx = height.length - 2;

        int[] rightMaxes = new int[height.length];
        for (int i = lastIdx; i >= 1; i--) {
            rightMaxes[i] = Math.max(rightMaxes[i + 1], height[i + 1]);
        }

        // 遍历每一根柱子,看看每一根柱子上能放多少水
        int water = 0, leftMax = 0;
        for (int i = 1; i <= lastIdx; i++) {
            leftMax = Math.max(leftMax, height[i - 1]);
            // 求出左边最大、右边最大中的较小者
            int min = Math.min(leftMax, rightMaxes[i]);
            // 说明这根柱子不能放水
            if (min <= height[i]) continue;
            // 说明这根柱子能放水
            water += min - height[i];
        }

        return water;
    }
}
LeetCode-42-接雨水(Trapping Rain Water)插图5
image-20210508092551689
/**
     * 空间复杂度O(1),时间复杂度O(n)
     */
class Solution {
     public static int trap(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int N = arr.length;
        int L = 1;
        int leftMax = arr[0];
        int R = N - 2;
        int rightMax = arr[N - 1];
        int water = 0;
        while (L <= R) {
            if (leftMax <= rightMax) {//遍历过程中,左侧的高度最大,小于右侧,以左侧高度结算水量 L++
                water += Math.max(0, leftMax - arr[L]);//leftMax - arr[L] 可能小于0,因为[L] 可以比左侧最高还高,新的左侧高度更新为[L]
                leftMax = Math.max(leftMax, arr[L++]);
            } else {
                water += Math.max(0, rightMax - arr[R]);
                rightMax = Math.max(rightMax, arr[R--]);
            }
        }
        return water;
    }
}
LeetCode-42-接雨水(Trapping Rain Water)插图6
image-20210508092826712
赞(0) 打赏
未经允许不得转载:IDEA激活码 » LeetCode-42-接雨水(Trapping Rain Water)

一个分享Java & Python知识的社区