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.length1 n 2 * 1040 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[len1], rightMax new int[len1]; 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; } }