JAVA练习270-接雨水

题目概览

给定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

来源：42. 接雨水 - 力扣（LeetCode）

解题分析

方法一：动态规划

按照每个格子的角度看，每个格子能达到的蓄水池深度取决于左右两边最高的格子，令左边最高为 leftMax[ i ]，右边最高为 rightMax[ i ]，当个格子蓄水深度为 dp[i]，可得：
dp[ i ] = min{ leftMax[ i ], rightMax[ i ] } - height[ i ]
先遍历获取左右两边最大高度，然后计算每个格子蓄水深度即可。

时间复杂度：O(n)
空间复杂度：O(n)

class Solution { public int trap(int[] height) { int result = 0, len = height.length; int[] leftMax = new int[len+1], rightMax = new int[len+1]; leftMax[0] = height[0]; rightMax[len-1] = height[len-1]; for (int i = 1; i < len; ++i) { leftMax[i] = Math.max(height[i], leftMax[i-1]); rightMax[len - 1 - i] = Math.max(height[len - 1 - i], rightMax[len - i]); } for (int i = 1; i < len; ++i) { result += Math.min(leftMax[i], rightMax[i]) - height[i]; } return result; } }

方法二：动态规划 + 双指针

由方法一得知，左边最高是从左往右遍历，右边最高是从右往左遍历，因此我们可以尝试使用双指针节省空间，令 i 在格子最左侧，j 在格子最右侧，如果 height[i] < height[j]，则 leftMax 一定也 < rightMax，因此可以得出：
当 height[i] <= height[j] 时，dp[i] = leftMax - height[i]；
当 height[i] > height[j] 时，dp[i] = rightMax - height[i]。

时间复杂度：O(n)
空间复杂度：O(1)

class Solution { public int trap(int[] height) { int result = 0, i = 0, j = height.length - 1, leftMax = 0, rightMax = 0; while(i < j) { leftMax = Math.max(height[i], leftMax); rightMax = Math.max(height[j], rightMax); if (height[i] < height[j]) { result += leftMax - height[i]; i++; }else { result += rightMax - height[j]; j--; } } return result; } }