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^4
• 0 <= height[i] <= 10^5

Java 实现解法

方法一：动态规划

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 来存储左右两侧的最高柱子高度。

方法二：双指针

java">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网站