给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)
数据范围：数组长度 
，数组中每个值满足 
，保证返回结果满足 
要求：时间复杂度 )
[编程题]接雨水问题
时间空间双98% 解法。从左往右找桶，累加容积；再从右往左找桶，累加容积。
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;
}
}
发表于 2022-04-16 15:45:02
回复(0)
代码提交成功平均运行 耗时 450 毫秒左右
1.首先求数组最大值a，定位索引位置；
2.根据最大值左右两边拆分数组，求左右两边数组最大值分别为多少，
3.左右两边最大值与数组最大值a之间的差值就是雨水；
4.同理循环上述即可；
# -*- 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] )
发表于 2022-02-09 13:11:37
回复(0)
这个题乍一看没有思路，但仔细研究就会发现，能不能装雨水主要取决于有没有“上下楼梯”的情况。我们假设有个数组是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;
}
}
发表于 2021-09-27 20:24:05
回复(1)
双指针，虽然每次i与j的值都是还没加入到ans里的值。但是每次更新都是变动的是leftMax与rightMax小的那一边的值。所以i与j会在最高峰相遇。此时while（i<j）与while(i<=j)会是一样的结果。
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;
}
};
发表于 2021-09-18 10:45:26
回复(0)
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;
}
}
发表于 2021-09-14 20:24:03
回复(0)
import java.util.*;
public class Solution {
public long maxWater (int[] arr) {
long sum=0;
int[] max_left=new int[arr.length],max_right=new int[arr.length];
for(int i=1;i<arr.length-1;i++){
max_left[i] = Math.max(max_left[i-1],arr[i-1]);
}
for(int i=arr.length-2;i>=0;i--){
max_right[i] = Math.max(max_right[i+1],arr[i+1]);
}
for(int i=1;i<arr.length-1;i++){
sum += Math.max(0,Math.min(max_left[i],max_right[i])-arr[i]);
}
return sum;
}
}
public class Solution {
public long maxWater (int[] arr) {
long sum=0;
int[] max_left=new int[arr.length],max_right=new int[arr.length];
for(int i=1;i<arr.length-1;i++){
max_left[i] = Math.max(max_left[i-1],arr[i-1]);
}
for(int i=arr.length-2;i>=0;i--){
max_right[i] = Math.max(max_right[i+1],arr[i+1]);
}
for(int i=1;i<arr.length-1;i++){
sum += Math.max(0,Math.min(max_left[i],max_right[i])-arr[i]);
}
return sum;
}
}
发表于 2021-08-22 20:04:39
回复(0)
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;
}
发表于 2021-07-15 10:30:50
回复(0)
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;
}
};
发表于 2021-07-08 13:50:04
回复(0)
解题思路：使用双指针，外循环终止条件为左指针与右指针相遇，内循环为，如果左边值小，则从左到右遍历，反之从右到左遍历
import java.util.*;
public class Solution {/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
//定义一个用来累加的变量
long count = 0L;
//定义起始的左边界
int from = 0;
//定义一个起始的右边界
int to = arr.length - 1;
while(from < to){
//找到最小的边界
int min=Math.min(arr[from],arr[to]);
while(from<to&&min>=arr[from]){
count+=min-arr[from];
from++;
}
while(from<to&&min>=arr[to]){
count+=min-arr[to];
to--;
}
}
return count;
}
}
发表于 2021-03-15 09:49:16
回复(0)
/**
* 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;
}
发表于 2021-02-28 17:03:47
回复(0)
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;
}
} 最好画个简单的柱图跟着代码的逻辑走一遍，就会恍然大悟，哈哈
编辑于 2020-12-06 18:19:38
回复(2)
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;
}
};
找水平线，不断更新水平线
发表于 2020-12-04 10:30:29
回复(0)
双指针。从左右端开始遍历。注意python会超时。https://www.nowcoder.com/questionTerminal/f92929ec6e5642a690e7c197b0c40e38?orderByHotValue=1&mutiTagIds=1579&page=1&onlyReference=false
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;
}
};
发表于 2020-09-27 11:14:52
回复(1)
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;
}
}
发表于 2021-04-20 01:18:53
回复(0)
思路：
1.按照反例思想，假设两个柱子（包括两个柱子）中间所有位置都可以存水，按照两个柱子里面，较低的那一根的高度，计算总存水量。接着减去，两个柱子间所有不可存水的块的数量（即数组里，两个位置间的值的和，这里面要包括两个较低柱子高度），最终得到两个柱子之间的可存水量。
2.寻找到最高的柱子的位置，从左向它去不断的找比左侧高的柱子，然后迭代更新左侧低柱子位置。
3.从右向最高柱子，进行同样的操作。
4.最终相加，完成总存水量的计算。
（注意：最后算总和的时候，要考虑数的溢出问题，转成long这个很关键）
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);
}
};
发表于 2020-12-30 18:23:42
回复(0)
将数组中每个位置上的累加起来就是总的水量
首先求容器边界,
然后使用双指针,
分别从两边往中间扫描,
当左边的高度小于右边的高度时,左指针++,
如果此时当前位置的高度小于容器的边界高度,这个位置上方有水,进行水量累加。
反之，则右指针向左扫描-1。
然后使用双指针,
分别从两边往中间扫描,
当左边的高度小于右边的高度时,左指针++,
如果此时当前位置的高度小于容器的边界高度,这个位置上方有水,进行水量累加。
反之，则右指针向左扫描-1。
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
}
编辑于 2021-01-13 15:59:55
回复(6)
题意与python题解
1、题意（题解区某大佬图）
与力扣 42.接雨水 一致
2、python题解
①python牛客有问题，返回1都能超时。以下题解已通过本地IDE
②动态编程法：遍历两遍，从左往右遍历保存当前最大值，从右往左遍历保存当前最大值，然后容水量为 两次遍历最大值中的最小值减去当前arr[i]。累加起来即可。（题解区某大佬C++改写）
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
③双指针（力扣Java官解改写）
我们先明确几个变量的意思：
left_max：左边的最大值，它是从左往右遍历找到的 right_max：右边的最大值，它是从右往左遍历找到的 left：从左往右处理的当前下标 right：从右往左处理的当前下标
定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。
定理二：当我们从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，但right_max对它而言是不可信的。（见下图，由于中间状况未知，对于left下标而言，right_max未必就是它右边最大的值）
定理三：当我们从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。
对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，这时候，如果left_max<right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。 所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标
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
编辑于 2021-03-23 14:09:41
回复(1)
双指针 i，j分别从两头向中间遍历，当i，j相同时循环终止。
思路：
1. 假设只有左右边界，中间的墙都是0，那么盛水量以最低的边界为准，所以后面更新边界的过程中，左边界更低就++i，右边界更低就--j
2. 实际情况中间可能存在比边界更高墙，从最低的边界遍历，比边界低的情况下，直接累加水量，遇到比边界更高的墙，说明当前坐标下的墙无法盛水，直接更新为边界。
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;
}
}
发表于 2021-01-31 13:54:01
回复(6)
class Solution {
public:
/**
* max water
* @param arr int整型vector the array
* @return long长整型
*/
long long maxWater(vector<int>& arr) {
long long sum=0;
int left=0,right=arr.size()-1;
//mark作为两边水位的最低边界
int mark=min(arr[left],arr[right]);
while(left<right)
{
if(arr[left]<arr[right])
{
left++;
if(arr[left]<mark)
sum+=mark-arr[left];
else
mark=min(arr[left],arr[right]);
}
else
{
right--;
if(arr[right]<mark)
sum+=mark-arr[right];
else
mark=min(arr[left],arr[right]);
}
}
return sum;
}
};
发表于 2021-08-15 19:49:51
回复(0)
问题信息
难度：
219条回答
1178收藏
12513浏览
通过挑战的用户
查看代码-
2023-01-12 23:52:11 -
2022-11-03 20:27:16 -
2022-10-05 21:51:23
-
2022-09-21 18:14:00 -
2022-09-20 14:46:14
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
