42. 接雨水
难度困难2330收藏分享切换为英文接收动态反馈
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
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.length0 <= n <= 3 * 1040 <= height[i] <= 105
- 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:
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.length0 <= n <= 3 * 1040 <= height[i] <= 105
image-20210508090145236
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;
}
}
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;
}
}
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;
}
}
image-20210508092826712
