LeetCode 42. 接雨水
题目描述
给定一个非负整数数组 height 表示柱状图中每个柱子的高度，请你计算按此排列的柱状图能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面的柱状图可以通过 6 个单位的雨水。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
0 <= height.length <= 10^40 <= height[i] <= 10^5
Java 实现解法
方法一：动态规划
class Solution {public int trap(int[] height) {if (height == null || height.length == 0) {return 0;}int n = height.length;int[] leftMax = new int[n];int[] rightMax = new int[n];leftMax[0] = height[0];for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], height[i]);}rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = Math.max(rightMax[i + 1], height[i]);}int water = 0;for (int i = 0; i < n; i++) {water += Math.min(leftMax[i], rightMax[i]) - height[i];}return water;}
}
解题思路
- 动态规划：这个问题可以通过两次遍历数组来解决。首先，我们从左到右遍历数组，记录每个位置左侧最高的柱子高度。然后，从右到左遍历数组，记录每个位置右侧最高的柱子高度。
- 计算雨水量：对于数组中的每个柱子，能接到的雨水量取决于其左右两侧最高的柱子高度中的较小值，减去该柱子的高度。这样，每个柱子能接到的雨水量就是
min(leftMax[i], rightMax[i]) - height[i]。 - 累加雨水量：遍历整个数组，将每个柱子能接到的雨水量累加起来，就得到了总的雨水量。
这种方法的时间复杂度是 O(n)，其中 n 是数组 height 的长度，因为我们对数组进行了三次遍历。空间复杂度是 O(n)，因为我们使用了两个额外的数组 leftMax 和 rightMax 来存储左右两侧的最高柱子高度。
方法二：双指针
class Solution {public int trap(int[] height) {int n = height.length;int left = 0, right = n - 1;int leftMax = 0, rightMax = 0;int water = 0;while (left < right) {if (height[left] <= height[right]) {if (height[left] >= leftMax) {leftMax = height[left];} else {water += leftMax - height[left];}left++;} else {if (height[right] >= rightMax) {rightMax = height[right];} else {water += rightMax - height[right];}right--;}}return water;}
}
解题思路
- 双指针：我们使用两个指针
left和right分别从数组的两端开始向中间移动。 - 维护最大高度：同时维护两个变量
leftMax和rightMax来记录left和right指针左侧和右侧的最大高度。 - 计算雨水量：当
height[left] <= height[right]时，我们移动left指针，并更新leftMax。如果height[left]小于leftMax，则这部分可以接到雨水，雨水量为leftMax - height[left]。类似地，当height[left] > height[right]时，我们移动right指针，并更新rightMax，计算雨水量。 - 累加雨水量：将每次计算得到的雨水量累加起来，得到总的雨水量。
这种方法的时间复杂度是 O(n)，其中 n 是数组 height 的长度，因为我们只遍历了数组一次。空间复杂度是 O(1)，因为我们只使用了常数个额外的变量，没有使用额外的空间。
注：来源leetcode网站