本文主要是介绍【NO.16】LeetCode经典150题-42. 接雨水,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 【NO.16】LeetCode经典150题-42. 接雨水
- 解题:动态规划
【NO.16】LeetCode经典150题-42. 接雨水
42. 接雨水
【困难】【HOT100】
给定 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
解题:动态规划
动态规划是用两个数组记录当前位置的左边遇到的最高高度,右边遇到的最高高度。然后取left right 两者中较小的 减去height[i] 就是当前位置水的高度。
// 时间空间都为O(n)
class Solution {public int trap(int[] height) {int length = height.length;int[] leftHeight = new int[length];int[] rightHeight = new int[length];// 获取当前位置左边的最大高度leftHeight[0] = height[0];for (int i = 1; i < length; i++) {leftHeight[i] = Math.max(leftHeight[i-1], height[i]);}// 获取当前位置右边的最大高度rightHeight[length-1] = height[length-1];for (int i = length-2; i >= 0; i--) {rightHeight[i] = Math.max(rightHeight[i+1], height[i]);}// 计算答案int ans = 0;for (int i = 0; i < length; i++) {ans += Math.min(leftHeight[i], rightHeight[i]) - height[i];}return ans;}
}
空间优化:
动态规划的做法中,需要维护两个数组 leftMax 和 rightMax,因此空间复杂度是 O(n)。
我们注意到下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。由于数组 leftMax 是从左往右计算,数组 rightMax 是从右往左计算,因此可以使用双指针和两个变量代替两个数组。
维护两个指针 left 和 right,以及两个变量 leftMax 和 rightMax,初始时left=0, right=n−1, leftMax=0, rightMax=0。指针 left 只会向右移动,指针 right 只会向左移动,在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。
当两个指针没有相遇时,进行如下操作:
-
使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值;
-
如果 height[left]<height[right],则必有 leftMax<rightMax,下标 left 处能接的雨水量等于 leftMax−height[left],将下标 left 处能接的雨水量加到能接的雨水总量,然后将 left 加 1(即向右移动一位);
-
如果 height[left]≥height[right],则必有 leftMax≥rightMax,下标 right 处能接的雨水量等于 rightMax−height[right],将下标 right 处能接的雨水量加到能接的雨水总量,然后将 right 减 1(即向左移动一位)。
当两个指针相遇时,即可得到能接的雨水总量。
// 时间O(n),空间O(1)
class Solution {public int trap(int[] height) {int length = height.length;int left = 0;int right = length-1;int leftMax = 0;int rightMax = 0;int ans = 0;// 相向而动while (left < right) {leftMax = Math.max(leftMax, height[left]);rightMax = Math.max(rightMax, height[right]);if (leftMax < rightMax) {ans += leftMax - height[left];left++;} else {ans += rightMax - height[right];right--;}}return ans;}
}
这篇关于【NO.16】LeetCode经典150题-42. 接雨水的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!