给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 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 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一开始想用优先队列试试,结果到最后没想出来。
发现可以先找到一个最高的,之后从两遍向最高的遍历,用两个变量来维护两边相对更高的。
每次都添加一列的雨水。
0 1 2 3 4 5 6 7 8 9 10 11
如图:第一次遍历找到下标为7的柱子(最高的柱子)
然后从左边开始遍历,一开始指针为0,到下标为1的位置后,更新指针,到2的位置后,res = res + height[left] - height[i]。下标为3:更新指针;下标为4:加2 - 1 = 1,下标为5:加2 - 0 = 2;下标为2:加2 - 1 = 6,7的位置更新指针,然后左遍历结束。
从右边开始遍历,一开始指针为11,下标为10的位置,更新指针。下标为9:加 2 - 1 = 1;下标为8:更新指针;下标为7:更新指针。右遍历结束。
class Solution { public int trap(int[] height) { int maxIndex = 0; for (int i = 0; i < height.length; i ++) { maxIndex = height[i] > height[maxIndex] ? i : maxIndex; } int res = 0; int left = 0; for (int i = 0; i <= maxIndex; i ++) { if (height[i] >= height[left]) { left = i; } else { res += height[left] - height[i]; } } int len = height.length - 1; int right = len; for (int i = len; i >= maxIndex; i --) { if (height[i] >= height[right]) { right = i; } else { res += height[right] - height[i]; } } return res; } }
进行优化,利用双指针同时向中间遍历,每次移动高度较小的那个指针。
如果遇到某个位置比另一边更低,则说明该位置必定可以装到另一边的位置。
class Solution { public int trap(int[] height) { int ans = 0; int left = 0, right = height.length - 1; int leftMax = 0, rightMax = 0; while (left < right) { leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); if (height[left] < height[right]) { ans += leftMax - height[left]; left ++; } else { ans += rightMax - height[right]; right --; } } return ans; } }