[3,1,2,5,2,4]
5
数组 [3,1,2,5,2,4] 表示柱子高度图,在这种情况下,可以接 5个单位的雨水,蓝色的为雨水 ,如题面图。
[4,5,1,3,2]
2
// 从短柱子的那一边开始做移动操作 public class Solution { public long maxWater (int[] arr) { int n = arr.length; int idx1 = 0, point1 = 0; int idx2 = n - 1, point2 = n - 1; long sum = 0; while (point1 != point2) { if (arr[idx1] > arr[idx2]) { point2--; if (arr[idx2] > arr[point2]) { sum += arr[idx2] - arr[point2]; } else { idx2 = point2; } } else { point1++; if (arr[idx1] > arr[point1]) { sum += arr[idx1] - arr[point1]; } else { idx1 = point1; } } } return sum; } }
public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { // write code here int vol = 0,left = 0, right = arr.length - 1; while( left < right){ //左边往右找,高度比当前高就能成桶 int leftSum = 0; for(int i = left + 1; i <= right ; i ++){ //成桶 if(arr[i] >= arr[left]){ //累加容积(容积 = 短板高度 * 长度 - 不能盛水的容积) vol += arr[left] * ( i - left + 1 - 2) - leftSum; //替换left为当前点 left = i; leftSum = 0; continue; } //统计中间不能盛水的地方 leftSum += arr[i]; } //右边同理,往左找 int rightSum = 0; for(int i = right - 1; i >= left ; i --){ //成桶 if(arr[i] >= arr[right]){ //累加容积 vol += arr[right] * (right - i + 1 - 2) - rightSum; //替换right为当前点 right = i; rightSum = 0; continue; } //统计中间不能盛水的地方 rightSum += arr[i]; } } return vol; } }
# -*- coding:utf-8 -*- def max_yu(list_yu): max_n = 0 i = 0 max_zhu_inedx = [] len_n = len(list_yu) max_zhu = max(list_yu) max_zhu_wzhi_c = list_yu.index(max_zhu) max_zhu_count = list_yu.count(max_zhu) if max_zhu_count == 1 and list_yu.count(list_yu[0]) == len_n-1: print(max_n) return max_n else: if max_zhu_count > 1: while i < len_n: if max_zhu == list_yu[i]: max_zhu_inedx.append(i) i += 1 min_zhu_index = min(max_zhu_inedx) max_zhu_index = max(max_zhu_inedx) if max_zhu_index - min_zhu_index == 1: max_n = 0 else: min_zhu_index_lshi = min_zhu_index while min_zhu_index_lshi < max_zhu_index: max_n = max_n + max_zhu - list_yu[min_zhu_index_lshi] min_zhu_index_lshi += 1 chushi = max_zhu_index while chushi < len_n: max_f1_list = list_yu[chushi + 1:] if len(max_f1_list) != 0: max_f1 = max(max_f1_list) max_f1_inedx = max_f1_list.index(max_f1) if max_f1_inedx == 0: chushi += 1 else: j = 0 while j < max_f1_inedx: max_n = max_n + max_f1 - max_f1_list[j] j += 1 chushi = max_f1_inedx + 1 + chushi else: chushi += 1 chushi = min_zhu_index while chushi > 0: max_f2_list = list_yu[:chushi] max_f2 = max(max_f2_list) max_f2_inedx = max_f2_list.index(max_f2) if max_f2_inedx == len(max_f2_list) - 1: chushi -= 1 else: j = max_f2_inedx while j < len(max_f2_list): max_n = max_n + max_f2 - max_f2_list[j] j += 1 chushi = max_f2_inedx return max_n else: max_zhu_inedx.append(max_zhu_wzhi_c) if len(max_zhu_inedx) == 1: chushi = max_zhu_wzhi_c while chushi < len_n: max_f1_list = list_yu[chushi+1:] if len(max_f1_list) != 0: max_f1 = max(max_f1_list) max_f1_inedx = max_f1_list.index(max_f1) if max_f1_inedx == 0: chushi += 1 else: j = 0 while j < max_f1_inedx: max_n = max_n + max_f1 - max_f1_list[j] j += 1 chushi = max_f1_inedx + 1 + chushi else: chushi += 1 chushi = max_zhu_wzhi_c while chushi > 0: max_f2_list = list_yu[:chushi] max_f2 = max(max_f2_list) max_f2_inedx = max_f2_list.index(max_f2) if max_f2_inedx == len(max_f2_list) - 1: chushi -= 1 else: j = max_f2_inedx while j < len(max_f2_list): max_n = max_n + max_f2 - max_f2_list[j] j += 1 chushi = max_f2_inedx return max_n max_yu([3,1,2,5,2,4] )
这个题乍一看没有思路,但仔细研究就会发现,能不能装雨水主要取决于有没有“上下楼梯”的情况。我们假设有个数组是12321.那么最高的元素是3,可以看到最高元素的左边如果满足“上楼梯”的情况,是装不到水的。同样,右边元素满足“下楼梯”也是装不到水的。那么如何判断“上楼梯”“下楼梯”的情况呢?只需要设置两个指针left,right。让这两个指针都从端点出发,在最高元素的左半部分,就让left不动,right向右移动。雨水量就是arr[left]>arr[right]时,也就是“下楼梯”,arr[left]-arr[right]就是接的雨水量。当arr[left]-arr[right]<0时,只需要再从当前right位置继续计算雨水量就行了。当然,在右半部分,只需保持right不动,left左移即可。
import java.util.*; public class Solution { public long maxWater (int[] arr) { int len = arr.length; if(len<=1)return 0; int top=arr[0],left=0,right,maxindex=0; long count=0; for(int j=0;j<len;++j){ if(top<arr[j]){ maxindex = j; top=arr[j]; } } for(left =0,right=0;right<maxindex;){ if(arr[left]>=arr[right]){ count = count+arr[left]-arr[right]; right++; } else left=right; } for(left =len-1,right=len-1;left>maxindex;){ if(arr[left]<=arr[right]){ count = count+arr[right]-arr[left]; left--; } else right=left; } return count; } }
class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 */ long long maxWater(vector<int>& arr) { // write code here int i=0; int j=arr.size()-1; long long ans=0; int leftMax=arr[i]; int rightMax=arr[j]; // while(i<=j){ if(leftMax<rightMax){ ans+=leftMax-arr[i]; i++; leftMax=std::max(leftMax,arr[i]); }else{ //这里leftMax>=rightMax,否则循环可能出不去 ans+=rightMax-arr[j]; j--; rightMax=std::max(rightMax,arr[j]); } } return ans; } };
public class Solution { public long maxWater (int[] arr) { // write code here int len = arr.length; int[] left = new int[len]; int[] right = new int[len]; left[0] = arr[0]; for(int i = 1; i < len; i++){ left[i] = Math.max(arr[i], left[i-1]); } right[len-1] = arr[len-1]; for(int i = len - 2; i >= 0; i--){ right[i] = Math.max(arr[i], right[i+1]); } long ans = 0; for(int i = 0; i < arr.length; i++){ ans += Math.min(left[i], right[i]) - arr[i]; } return ans; } }
long long maxWater(vector<int>& arr) { // write code here int n=arr.size(); long long maxWater=0; int l=0,r=n-1; long long minWater=min(arr[l],arr[r]); while(l<r){ if(arr[l]>arr[r]){ r--; if(arr[r]>=minWater){ minWater=min(arr[l],arr[r]); }else{ maxWater+=minWater-arr[r]; } }else{ l++; if(arr[l]>=minWater){ minWater=min(arr[l],arr[r]); }else{ maxWater+=minWater-arr[l]; } } } return maxWater; }
class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 */ long long maxWater(vector<int>& height) { const int n = height.size(); int peakIndex = max_element(begin(height), end(height)) - begin(height); long ans = 0; int leftMostBar = 0; for (int i = 0; i < peakIndex; ++i) { if (height[i] > leftMostBar) leftMostBar = height[i]; else ans += leftMostBar - height[i]; } int rightMostBar = 0; for (int i = n - 1; i > peakIndex; --i) { if (height[i] > rightMostBar) rightMostBar = height[i]; else ans += rightMostBar - height[i]; } return ans; } };
a[left, right] 是一个水槽, 递归的看,可能中间存在某个mid, a[left, mid]也是水槽,a[mid, right]也是水槽,那么怎么解决这个递归问题呢?
本人的方法是用一把刀横着去切水槽:sum表示水槽容积
1.假设用一把 刀 横着去切这个水槽 a[left, right] 那么从哪边开始切呢?当然是从小的一边开始切
if a[left] <= a[right] 从左边向右切一刀水槽:
怎么切?没有遇到挡住的障碍,说明可以装水,一路切过去,同时计算sum += a[left] - a[l]
if a[left] > a[right] 从右边向左切一刀水槽:
怎么切?没有遇到挡住的障碍,说明可以装水,一路切过去,同时计算sum += a[right] - a[r]
2.切完一次,left 和 right 重新移到递归小水槽的两边, 于是又递归成了切水槽问题(计算水槽容积问题),返回 1 计算,直到 l = r
class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 */ long long maxWater(vector<int>& arr) { int l =0, r = arr.size()-1; long long sum=0; //注意要long long 否则很可能加法溢出 while(l<r){//左右不等,没砍完 if(arr[l] <= arr[r]){ // 左边比右边小,从左边开始砍 int left = arr[l]; //基准 while(l+1<r && arr[l+1]< left){ //如果右边一个位置比基准矮,刀无阻碍 sum += (left-arr[l+1]); //刀下方可以装水 l++; } l++; //刀遇到到第一个碰瓷(碰刀)的柱子 } else{ //否则从右边开始切 int right = arr[r]; //以右边最低为基准 while(r-1>l && arr[r-1] < right){//如果左边一个位置比基准矮,刀无阻碍 sum += (right -arr[r-1]); //刀下方装水 r--; } r--; //向左移移到第一个碰瓷(碰刀)的柱子 } } return sum; } };
/** * max water * @param arr int整型一维数组 the array * @param arrLen int arr数组长度 * @return long长整型 */ long long maxWater(int* arr, int arrLen ) { if (arrLen <= 2) { return 0; } long long res = 0; int left = 0; int right = arrLen - 1; int maxLeft = arr[left]; int maxRight = arr[right]; while (left < right) { if (maxLeft < maxRight){ left++; if (maxLeft < arr[left]) { maxLeft = arr[left]; } else { res += maxLeft - arr[left]; } } else { right--; if (maxRight < arr[right]) { maxRight = arr[right]; } else { res += maxRight - arr[right]; } } } return res; }
import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { // write code here long res=0; int left_Height,right_Height; int left=0,right=arr.length-1; while(left<right){ left_Height=arr[left]; right_Height=arr[right]; if(left_Height<right_Height){ while(left<right&&arr[left]<=left_Height){ res+=left_Height-arr[left]; left++;//left++更新左侧最高的柱子,同下面right--对应,镜像,当while条件不满 //足时,结束当前计算循环 } }else{ while(left<right&&arr[right]<=right_Height){ res+=right_Height-arr[right]; right--; } } } return res; } }最好画个简单的柱图跟着代码的逻辑走一遍,就会恍然大悟,哈哈
class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 */ long long maxWater(vector<int>& arr) { int l = 0, r = arr.size() - 1; long long ans = 0; int lmax = 0, rmax = 0; while(l < r) { lmax = max(lmax, arr[l]); rmax = max(rmax, arr[r]); if(lmax < rmax) { ans += lmax - arr[l++]; } else { ans += rmax - arr[r--]; } } return ans; } };找水平线,不断更新水平线
class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 */ long maxWater(vector<int> &arr) { // write code here int n = arr.size(); if (n <= 2) return 0; int i = 0, j = n - 1, left = arr[0], right = arr[n - 1]; long long sum_val = 0; while (i < j) { if (left < right) { i++; if (arr[i] >= left) { left = arr[i]; continue; } sum_val += (left - arr[i]); } else { j--; if (arr[j] > right) { right = arr[j]; continue; } sum_val += (right - arr[j]); } } return sum_val; } };
public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { if (arr == null || arr.length == 0) return 0L; long ans = 0; int left = 0, right = arr.length - 1; int lmax = arr[left], rmax = arr[right]; while (left < right) { lmax = Math.max(arr[left], lmax); rmax = Math.max(arr[right], rmax); if (lmax <= rmax) ans += lmax - arr[left++]; else ans += rmax - arr[right--]; } return ans; } }
class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 */ void find_max(vector<int> arr, int &index) //遍历一遍找到最大的值,以及最大的索引 { int max_num = arr[0]; index = 0; int temp_max = 0; for (int i = 1; i < arr.size(); i++) { temp_max = arr[i]; if (temp_max > max_num) { max_num = temp_max; index = i; } } } long long maxWater(vector<int>& arr) { long long temp_block = arr[0]; long long temp_whole = 0; int max_index = 0; if (arr.size() == 1) return 0; find_max(arr, max_index); //先找到最大值的位置 //从左向最大值,寻找最多存水 int left = 0; long long lf_sum = 0; temp_block = arr[0]; temp_whole = 0; for (int i = 1; i <= max_index; i++) { if (arr[i] >= arr[left]) //比左侧的相等,或者高了,来计算一波存水量 { temp_whole = long(arr[left]) * (i - left + 1); //假设整个区间都可以存水 temp_block += arr[left]; lf_sum = lf_sum + (temp_whole - temp_block); //减去中间被占用到的存水的位置 temp_block = arr[i]; left = i; } else //没有左侧那么高,直接累加起来 temp_block += arr[i]; } //从右向最大值,寻找最多存水 int right = arr.size() - 1; long long rh_sum = 0; temp_block = arr[right]; temp_whole = 0; for (int i = right - 1; i >= max_index; i--) { if (arr[i] >= arr[right]) //比右侧的相等,或者高了,来计算一波 { temp_whole = long(arr[right]) * (right - i + 1); //假设整个区间都可以存水 temp_block += arr[right]; rh_sum = rh_sum + (temp_whole - temp_block); //减去中间被占用到的存水的位置 temp_block = arr[i]; right = i; } else //没有那么高,直接累加起来 temp_block += arr[i]; } //最后返回两侧存水之和 return (lf_sum + rh_sum); } };
function maxWater( arr ) { // write code here if(arr == null || arr.length<3) return 0 let l = 0,r = arr.length-1, area = 0 let min = Math.min(arr[l],arr[r]) while(l<r){ if(arr[l]<arr[r]){ l++ if(arr[l]<min){ area += min - arr[l] }else { min = Math.min(arr[l],arr[r]) } }else{ r-- if(arr[r]<min){ area +=min-arr[r] }else { min = Math.min(arr[r],arr[l]) } } } return area }
class Solution: def maxWater(self , arr ): # write code here le = len(arr) l = list([0] * le) r = list([0] * le) l[0] = arr[0] r[le - 1] = arr[le - 1] for i in range(1, le): l[i] = max(l[i - 1], arr[i]) r[le - i - 1] = max(r[le - i], arr[le - i - 1]) res = 0 for i in range(1, le - 1): if min(l[i], r[i]) - arr[i] > 0: res += min(l[i], r[i]) - arr[i] return res
我们先明确几个变量的意思:
left_max:左边的最大值,它是从左往右遍历找到的 right_max:右边的最大值,它是从右往左遍历找到的 left:从左往右处理的当前下标 right:从右往左处理的当前下标
定理一:在某个位置i处,它能存的水,取决于它左右两边的最大值中较小的一个。
定理二:当我们从左往右处理到left下标时,左边的最大值left_max对它而言是可信的,但right_max对它而言是不可信的。(见下图,由于中间状况未知,对于left下标而言,right_max未必就是它右边最大的值)
定理三:当我们从右往左处理到right下标时,右边的最大值right_max对它而言是可信的,但left_max对它而言是不可信的。
class Solution: def maxWater(self, arr ): left, right, res, left_max, right_max = 0, len(arr) - 1, 0, 0, 0 while left < right: if arr[left] < arr[right]: if arr[left] > left_max: left_max = arr[left] else: res += left_max - arr[left] left += 1 else: if arr[right] > right_max: right_max = arr[right] else: res += right_max - arr[right] right -= 1 return res
public class Solution { public long maxWater (int[] arr) { int l = 0, r = arr.length - 1, i = l, j = r; long v = 0; while (i < j) { if (arr[l] < arr[r]) { if (arr[++i] < arr[l]) { v += arr[l] - arr[i]; } else { l = i; } } else { if (arr[--j] < arr[r]) { v += arr[r] - arr[j]; } else { r = j; } } } return v; } }