动态规划
对于下标 i:
下雨后水能到达的最大高度等于下标 i两边的最大高度的最小值,
下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 arr[i]。
步骤:
1.做法是对于数组 arr中的每个元素,分别向左和向右扫描并记录左边和右边的最大高度。
2.对于数组 arr中的每个元素,能接的雨水量等于下标 i 处的水能到达的最大高度减去 arr[i]。能到达的最大高度分别向左和向右扫描并记录左边和右边的最大高度的最小值。
代码如下:
import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { // write code here long sum=0; int[] leftMax=new int[arr.length]; int[] rightMax=new int[arr.length]; //向左扫描并记录左边和右边的最大高度 for(int i=1;i<arr.length-1;i++){ leftMax[i] = Math.max(leftMax[i - 1], arr[i - 1]); } //向右扫描并记录左边和右边的最大高度 for (int i = arr.length - 2; i >= 0; i--) { rightMax[i] = Math.max(rightMax[i + 1], arr[i + 1]); } //能接的雨水量等于下标 i 处的水能到达的最大高度减去 arr[i] //能到达的最大高度分别向左和向右扫描并记录左边和右边的最大高度的最小值 for (int i = 1; i < arr.length; i++) { int min = Math.min(leftMax[i], rightMax[i]); if (min > arr[i]) { sum += (min - arr[i]); } } return sum; } }上述解法使用了dp的思想,时间和空间复杂度为o(n),对于dp的优化,可以使用有限的几个变量使得空间复杂度降为o(1).
代码如下:
import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] height) { // write code here long ans = 0; //左右边界 int left = 0, right = height.length - 1; //维护最大值 int leftMax = 0, rightMax = 0; while (left < right) { leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); if (height[left] < height[right]) { //如何证明若 height[left] < height[right] 必有 leftmax < rightmax //左指针右移的终止条件是找到比 rightmax 大的 leftmax, //也就是说一旦左指针终止左移,此时的height[left] 一定是 leftmax,且大于 rightmax。 //同理,右指针左移的终止条件是找到比 leftmax 大的 rightmax, //而此时的 height[right] 就是 rightmax。 //所以这里 height[left] < height[right] 中的 height[right] 就是当前的 rightmax, //而 height[left] < height[right](rightmax)意味着还没找到大于 rightmax 的 leftmax,所以 leftmax < rightmax ans += leftMax - height[left];//leftMax就是两者的最小值 ++left; } else { ans += rightMax - height[right];//rightMax就是两者的最小值 --right; } } return ans; } }其中,如何证明若 height[left] < height[right] 必有 leftmax < rightmax?代码给了注释,但是我还是没有很理解,我是讲给定的示例模拟一遍发现确实符合。