给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)
数据范围：数组长度 
，数组中每个值满足 
，保证返回结果满足 
要求：时间复杂度 )
[编程题]接雨水问题
public long maxWater (int[] arr) {
// 双指针 每次只计算一个格子的
int left=0;
int right=arr.length-1;
if(arr==null) return 0L;
long ans=0;
int maxL=0;
int maxR=0;
while(left<right){
//每次维护中间的最大边界
maxL=Math.max(maxL,arr[left]);
maxR=Math.max(maxR,arr[right]);
//判断哪边是较短的，统计水量
if(maxR>maxL){
ans=ans+(maxL-arr[left]);
left++;
}else{
ans=ans+(maxR-arr[right]);
right--;
}
}
return ans;
}
发表于 2023-07-24 10:20:16
回复(0)
public class Solution {
public long maxWater (int[] arr) {
// write code here
int length = arr.length;
int left = 0;
int right = length - 1;
long sum = 0L;
int lowMark = Math.min(arr[left], arr[right]);
while (left < right) {
if (arr[left] < arr[right]) {
left++;
if (arr[left] < lowMark) sum += lowMark - arr[left];
else lowMark = Math.min(arr[left], arr[right]);
} else {
right--;
if (arr[right] < lowMark) sum += lowMark - arr[right];
else lowMark = Math.min(arr[left], arr[right]);
}
}
return sum;
}
}
发表于 2023-03-21 18:39:48
回复(0)
import java.util.*;
public class Solution {
public long maxWater (int[] arr) {
// write code here
int l = 0, r = arr.length - 1;
int ans = 0, lmax = 0, rmax = 0;
while (l < r) {
//找左右两边最高的高度
lmax = Math.max(lmax, arr[l]);
rmax = Math.max(rmax, arr[r]);
//接雨水由最短的板子决定，计算雨量和移动短板
if (lmax < rmax) {
ans += lmax - arr[l];
l++;
} else {
ans += rmax - arr[r];
r--;
}
}
return ans;
}
}
发表于 2023-01-28 14:38:29
回复(0)
我也不知道自己咋写的
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
int left = 0;
int right = 1;
int temp= 0;
int res = 0;
while(right<arr.length){
if(arr[left]>arr[right]){
temp+=arr[left]-arr[right];
right++;
}else{
res+=temp;
temp =0;
left = right;
right++;
}
}
if(temp == 0){
return res;
}
int rever= arr.length-2;
temp = 0;
right--;
while(rever>=left){
if(arr[rever]<arr[right]){
temp+=arr[right]-arr[rever];
rever--;
}else{
res +=temp;
temp=0;
right = rever;
rever--;
}
}
return res;
}
}
发表于 2022-11-22 21:34:50
回复(0)
灵机一动，写出了非常简洁的代码，参考知乎大神 https://zhuanlan.zhihu.com/p/436613867 的做法
在力扣运行成功，时间100%
class Solution {
public int trap(int[] height) {
int l=0,r=height.length -1,lnum=height[l],rnum=height[r],res=0;
while(l<r){
if(lnum<=rnum){
l++;
res += Math.max(lnum-height[l],0);
lnum = Math.max(lnum, height[l]);
}
else{
r--;
res += Math.max(rnum - height[r], 0);
rnum = Math.max(rnum, height[r]);
}
}
return res;
}
}
发表于 2022-09-30 20:28:30
回复(0)
import java.util.ArrayList;
public class Solution {
public long maxWater (ArrayList<Integer> arr) {
int i = 0;
int j = arr.size()-1;
int sum = 0;
int min = Math.min(arr.get(i),arr.get(j));
while(i<j){
if(arr.get(i)<arr.get(j) && i<j){
while(arr.get(i)<=min){
sum =sum-arr.get(i)+min;
i++;
}
min = Math.min(arr.get(i),arr.get(j));
}else{
while(arr.get(j)<=min && i<j){
sum= sum-arr.get(j)+min;
j--;
}
min = Math.min(arr.get(i),arr.get(j));
}
}
return sum;
}
}
发表于 2022-09-29 11:54:27
回复(0)
暴力求解
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
if (arr == null || arr.length <= 2) {
return 0;
}
int start = 0;
List<Count> valid = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
Count between = between(start, arr);
if (between.isValid()) {
valid.add(between);
}
if (between.isOver()) {
break;
}
start = between.getEnd();
}
long total = 0L;
for (Count count : valid) {
int min = Math.min(arr[count.getEnd()], arr[count.getStart()]);
for (int i = count.getStart() + 1; i < count.getEnd(); i++) {
total += min - arr[i];
}
}
return total;
}
public Count between(int start, int[] arr) {
Count count = new Count();
if (start >= arr.length - 2) {
count.setOver(true);
return count;
}
if (arr[start + 1] >= arr[start]) {
count.setValid(false);
count.setEnd(start + 1);
return count;
}
/*只剩下降趋势*/
count.setStart(start);
int flag = 1;
int mid = start;
while (mid < arr.length) {
if (mid == arr.length - 1) {
count.setOver(true);
return count;
}
/*下降趋势*/
if (arr[mid + 1] < arr[mid]) {
/*第一次下降 最小值修改 end修改 继续*/
if (flag == 1) {
count.setEnd(mid + 1);
}
/*第二次下降 有效区间 end修改*/
if (flag == 2) {
count.setValid(true);
count.setEnd(mid);
break;
}
}
/*等高*/
if (arr[mid] == arr[mid + 1]) {
count.setEnd(mid + 1);
}
/*增长趋势*/
if (arr[mid + 1] > arr[mid]) {
/*转折点*/
if (flag == 1) {
count.setEnd(mid + 1);
count.setValid(true);
flag = 2;
}
/*不可能出现 flag==2 且是增长趋势*/
count.setEnd(mid + 1);
}
mid++;
}
/*找寻更高的结束*/
if (count.isValid() && arr[count.getStart()] >= arr[count.getEnd()]) {
for (int i = count.getEnd(); i < arr.length; i++) {
if (arr[i] >= arr[count.getStart()]) {
count.setEnd(i);
break;
}
if (arr[i] >= arr[count.getEnd()]) {
count.setEnd(i);
}
}
}
return count;
}
public static class Count {
int start ;
int end;
boolean valid;
boolean over;
public int getStart() {
return start;
}
public void setStart(int start) {
this.start = start;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
public boolean isValid() {
return valid;
}
public void setValid(boolean valid) {
this.valid = valid;
}
public boolean isOver() {
return over;
}
public void setOver(boolean over) {
this.over = over;
}
}
}
发表于 2022-09-19 17:11:29
回复(0)
public long maxWater (int[] arr) {
// write code here
long count = 0;
int j;
int i=0;
int k=1 ;
for( i=0 ;i <arr.length;){
for(j = i+1;j<=arr.length-1;j++){
if(arr[i]>=arr[j]){
count+= arr[i]-arr[j];
i++;
}
else {
k = 0;
i = j;
break;
}
}
}
return count;
}
}
// write code here
long count = 0;
int j;
int i=0;
int k=1 ;
for( i=0 ;i <arr.length;){
for(j = i+1;j<=arr.length-1;j++){
if(arr[i]>=arr[j]){
count+= arr[i]-arr[j];
i++;
}
else {
k = 0;
i = j;
break;
}
}
}
return count;
}
}
发表于 2022-09-09 10:30:10
回复(1)
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
if (arr.length < 3) return 0;
int le = 0, ri = arr.length - 1;
int maxl = 0, maxr = 0, res = 0;
while (le < ri) {
maxl = Math.max(maxl, arr[le]);
maxr = Math.max(maxr, arr[ri]);
//
res += maxl < maxr ? maxl - arr[le++] : maxr - arr[ri--];
}
return res;
}
}
发表于 2022-09-02 22:36:11
回复(0)
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
int V=0;
int[] leftmax=new int[arr.length];
int[] rightmax=new int[arr.length];
leftmax[0]=arr[0];
rightmax[arr.length-1]=arr[arr.length-1];
for(int i=1;i<=arr.length-1;i++){
leftmax[i]=Math.max(leftmax[i-1],arr[i]);
}
for(int i=arr.length-2;i>=0;i--){
rightmax[i]=Math.max(rightmax[i+1],arr[i]);
}
for(int i=0;i<=arr.length-1;i++){
if(leftmax[i]!=arr[i]&&rightmax[i]!=arr[i]){
V=V+Math.min(leftmax[i],rightmax[i])-arr[i];
}
}
return V;
}
}
发表于 2022-08-18 20:01:37
回复(0)
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
int left = 0, right = arr.length - 1;
int sum = 0, height = 0;
while (left < right) {
if (arr[left] < arr[right]) {
height = Math.max(height, arr[left]);
sum = sum + height - arr[left];
left ++;
} else {
height = Math.max(height, arr[right]);
sum = sum + height - arr[right];
right--;
}
}
return sum;
}
}
发表于 2022-08-03 11:50:07
回复(0)
看了答案的思路，然后自己写的，发现和答案的写法好像不太一样❓（不过讨论里有和我一样思路的）
开始想了半天怎么用Deque之类的来实现，然后发现没用到双指针，并且想法越来越复杂，直到放弃......
让我缓缓，等会再去看下答案的写法🥲
public long maxWater5 (int[] arr) {
long res = 0;
int i = 0, j = arr.length - 1;
while (i < j) {
long min = Math.min(arr[i], arr[j]); // 保存边界中的较小值
if (arr[i] < arr[j]) { // 若「左边界」较小，i指针右移计算蓄水量
while (arr[++i] < min) res += (min - arr[i]); // 一次性移动完毕，到第一个高度 ≥ 左边界的柱子
} else { // 同理，「右边界」对称移动
while (arr[--j] < min) res += (min - arr[j]);
}
}
return res;
}
发表于 2022-06-17 22:47:57
回复(0)
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
int l = 0;
long w = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] >= arr[l]) {
int tall = Math.min(arr[i] , arr[l]);
for (int k = l + 1;k<=i - 1;k++) {
w = w + (tall - arr[k] > 0?tall - arr[k]:0);
}
l = i;
continue;
}
}
l = arr.length - 1;
for (int i = arr.length - 2; i >= 0; i--) {
if (arr[i] > arr[l]) {
int tall = Math.min(arr[i] , arr[l]);
for (int k = i+1;k<=l-1;k++) {
w = w + (tall - arr[k] > 0?tall - arr[k]:0);
}
l = i;
continue;
}
}
return w;
}
}
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
int l = 0;
long w = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] >= arr[l]) {
int tall = Math.min(arr[i] , arr[l]);
for (int k = l + 1;k<=i - 1;k++) {
w = w + (tall - arr[k] > 0?tall - arr[k]:0);
}
l = i;
continue;
}
}
l = arr.length - 1;
for (int i = arr.length - 2; i >= 0; i--) {
if (arr[i] > arr[l]) {
int tall = Math.min(arr[i] , arr[l]);
for (int k = i+1;k<=l-1;k++) {
w = w + (tall - arr[k] > 0?tall - arr[k]:0);
}
l = i;
continue;
}
}
return w;
}
}
发表于 2022-05-22 20:59:20
回复(0)
问题信息
难度：
61条回答
1119收藏
9963浏览
通过挑战的用户
-
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号
