容积问题

给定一个非负数的数组，代表一个容器，例如数组[0,1,0,2,1,0,1,3,2,1,2,1]，就是以下图形中黑色的部分，如果用这个容器接水的话，请问可以接多少水，还以这个数组为例，可以接6格水，即以下蓝色部分。

要求：实现时间复杂度O(N),额外的空间复杂度O(1)的解法。

解法：任取一个数i，求其左边的最大值，右边的最大值，去其较小的最大值，则在数i上，可以存水较小的最大值与i之差。
方法1：遍历最大值求解的话时间复杂度为O(n²)
方法2：建立两个辅助数组L[i],R[i]，L[i]表示z从第0个数到第i个数的最大值，R[i]表示从当前第i个数到最后一个数的最大值。时间复杂度为O（N）
方法3：只准备一个辅助数组R[i]
方法4：LMax，RMax，L，R，L和R是左右两个指针，LMax和RMax表示左右两个指针左右的最大值，LMax和RMax较小的一边，靠近较小的指针的数先被结算。

给定一个非负数的数组，代表一个容器，例如数组[0,1,0,2,1,0,1,3,2,1,2,1]，就是以下图形中黑色的部分，如果用这个容器接水的话，请问可以接多少水，还以这个数组为例，可以接6格水，即以下蓝色部分。 要求：实现时间复杂度O(N),额外的空间复杂度O(1)的解法。解法：任取一个数i，求其左边的最大值，右边的最大值，去其较小的最大值，则在数i上，可以存水较小的最大值与i之差。 方法1：遍历最大值求解的话时间复杂度为O(n²) 方法2：建立两个辅助数组L[i],R[i]，L[i]表示z从第0个数到第i个数的最大值，R[i]表示从当前第i个数到最后一个数的最大值。时间复杂度为O（N） 方法3：只准备一个辅助数组R[i] 方法4：LMax，RMax，L，R，L和R是左右两个指针，LMax和RMax表示左右两个指针左右的最大值，LMax和RMax较小的一边，靠近较小的指针的数先被结算。public static int getWater(int[] arr){if(arr == null|| arr.length < ){return 0;}int value = 0;for(int i = 1; i<arr.length -1 ;i++){int leftMax = 0;int rightMax = 0;for(int l = 1;l< i ;l++){leftMax = Math.max(arr[l], leftMax);}for(int r = i;r < arr.length;r++){rightMax = Math.max(arr[r], rightMax);}value += Math.max(0, Math.max(leftMax, rightMax) - arr[i]);}return value; }public static int getWater(int[] arr){if(arr == null || arr.length < 3){return 0;}int n = arr.length - 2;int[] leftMaxs = new int[n];leftMaxs[0] = arr[0];for(int i = 1;i<n;i++){leftMaxs[i] = Math.max(leftMaxs[i-1], arr[i]);}int[] rightMaxs = new int[n];rightMaxs[n-1] = arr[n+1];for(int i = n-2; i>=0;i--){rightMaxs[i] = Math.max(rightMaxs[i+1],arr[i+2]);}int value = 0;for(int i = 1; i<= n;i++){value += Math.max(0,Math.min(leftMax[i-1], rightMax[i-1]-arr[i]));}return value; }public static int getWater(int[] arr){if(arr == null || arr.length < 3){return 0;}int n = arr.length - 2;int[] rightMaxs = new int[n];rightMaxs[n-1] = arr[n+1];for(int i = n-2; i>=0;i--){rightMaxs[i] = Math.max(rightMaxs[i+1],arr[i+2]);}int leftMax = arr[0];int value = 0;for(int i = 1; i<= n;i++){value += Math.max(0,Math.min(leftMax[i-1], rightMax[i-1]-arr[i]));leftMax = Math.max(leftMax,arr[i]);}return value; }public static int getWater(int[] arr){if(arr == null || arr.length < 3){return 0;}int value = 0;int leftMax = arr[0];int rightMax = arr[arr.length - 1];int l = 1;int r = arr.length - 2;while(l <= r){if(leftMax <= rightMax){value += Math.max(0, leftMax - arr[l]);leftMax = Math.max(leftMax, arr[l++]);}else{value += Math,max(0, rightMax - arr[r]);rightMax = Math.max(rightMax, arr[r--]);}}return value; }

总结

以上是生活随笔为你收集整理的容积问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。