终于要讲这道毒瘤面试题了,据说字节跳动保洁阿姨都能写出来 0.0
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
输入: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 个单位的雨水(蓝色部分表示雨水)。
分析
初步看有点像 LeetCode热题100——11. 盛最多水的容器,也是盛水问题,但这里复杂的是盛水的面积是不规则的,不能像11这道题一样直接长乘宽得到,那怎么办呢?
- 分治思路
遍历每个柱子,记录每个柱子能蓄多少水,最终把所有柱子的蓄水量求和就是答案 - 如何确定每个柱子的蓄水量? 柱子左右必须有比本身高的柱子才能蓄水
- 柱子为 nums[0] 或者 nums[length-1]时,water =0 , 边界处无法蓄水 (水满自溢)
- 柱子i∈ [1,length-2],左边最高柱子leftMax, 右边最高柱子 rightMax时
1. nums[i] < min(leftMax,rightMax) 可以蓄水,water = max(0, min(leftMax,rightMax) - nums[i])
2. nums[i] >= min(leftMax,rightMax) water = 0 (缺乏边界,无法蓄水)
代码
public int trap(int[] nums) {
int leftMax = nums[0];
int rightMax = nums[nums.length - 1];
int left = 1, right = nums.length - 2;
int res = 0;
while (left <= right) {
if (leftMax <= rightMax) {
if (nums[left] > leftMax) {
leftMax = nums[left];
} else {
res += leftMax - nums[left];
}
left++;
} else {
if (nums[right] > rightMax) {
rightMax = nums[right];
} else {
res += rightMax - nums[right];
}
right--;
}
}
return res;
}