给出n个数字,表示一个高程图,高程图中每一条的宽度为1,请计算下雨之后这个地形可以存储多少水
例如
给出[0,1,0,2,1,0,1,3,2,1,2,1],返回6.
上面的高程图用数组[0,1,0,2,1,0,1,3,2,1,2,1]表示。在这种情况下,6个单位的雨水(蓝色部分)被存储。
class Solution { public: int trap(int heights[], int n) { int maxhigh=0; int left=0,right=0; for(int i=0;i<n;i++)//找到最大值的下标 { if(heights[i]>heights[maxhigh]) maxhigh=i; } int sum=0; for(int i=0;i<maxhigh;i++)//计算左边的容量 { if(heights[i]<left) sum+=(left-heights[i]); else left=heights[i]; } for(int j=n-1;j>maxhigh;j--)//计算右边的容量 { if(heights[j]<right) sum+=(right-heights[j]); else right=heights[j]; } return sum; } };
int trap(int A[], int n) { stack<int> s; int res=0; for(int i=0;i<n;i++) { /* 如果新的高度比保存的s.top()高,证明找到右边界,可以计算,此处应为while 因为一次只能处理一层,如 2 1 0 2 ,先处理1 0 2 部分 填充1,然后继续计算2112计算2 */ while(!s.empty() && A[s.top()]<A[i]) { int t =s.top(); s.pop(); while(!s.empty() && A[s.top()]<=A[t]) s.pop(); if(!s.empty()) res+= (std::min(A[s.top()],A[i])-A[t])*(i-s.top()-1); } s.push(i); } return res; }
class Solution { public: int trap(int A[], int n) { if (n <= 2) return 0; int lefttop = A[0], righttop = A[n - 1]; int i = 1, j = n - 2; int sums = 0; while (i <= j) { if (lefttop > righttop) { sums += max(0, righttop - A[j]); righttop = max(righttop, A[j]); --j; } else { sums += max(0, lefttop - A[i]); lefttop = max(lefttop, A[i]); ++i; } } return sums; } };
public class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0){
return 0;
}
int max = 0;
int v = 0;
int[] container = new int[height.length];
for (int i = 0; i < height.length; i++) {
container[i] = max;
max = Math.max(max, height[i]);
}
max = 0;
for (int i = height.length - 1; i >= 0; i--) {
container[i] = Math.min(max, container[i]);
max = Math.max(max, height[i]);
v += container[i] - height[i] > 0 ? container[i] - height[i] : 0;
}
return v;
}
}
运行时间:5ms
占用内存:612k
//简单暴力的方法:一层一层的算,比如所给例子中第一层有2个坑,第二层有4个坑,一共有6个坑 //关键就是怎么把序列转成一层层,可以这样转: //{0,1,0,2,1,0,1,3,2,1,2,1} //第一层:遍历元素>=1的都为1,<1的为0,{0,1,0,1,1,0,1,1,1,1,1,1}调用cal算坑数 //第二层:遍历元素>=2的都为1,<2的为0,{0,0,0,1,0,0,0,1,1,0,1,0}调用cal算坑数 //第三层:遍历元素>=3的都为1,<3的为0,{0,0,0,0,0,0,0,1,0,0,0,0} class Solution public: int cal(int B[],int n) { int j=0,sum=0; bool flag=true; for(int i=0;i<n;i++) { if(B[i]==1 && flag){ j=i; flag=false;} else if(B[i]==1 && !flag) {sum+=i-j-1; flag=true; i--;} } return sum; } int trap(int A[], int n) { int MAX=0; for(int i=0;i<n;i++)//找层数 { if(A[i]>MAX) MAX=A[i]; } int B[n]; int res=0; for(int i=1;i<=MAX;i++) { for(int j=0;j<n;j++) { if(A[j]>=i) B[j]=1; else B[j]=0; } res+=cal(B,n); } return res; } };
磕磕绊绊写出来了...再碰上的话写出来也难
import java.util.Stack; public class Solution { public int trap(int[] A) { int len = A.length; Stack<Integer> stack = new Stack<>(); int trap = 0; for (int i = 0; i < len; i++) { int hCur = A[i]; int hPre = stack.empty() ? 0 : A[stack.peek()]; if (hCur > hPre && !stack.empty()) { hPre = A[stack.pop()]; int left = stack.empty() ? 0 : stack.peek(); int distance; if (A[left] > hCur) { distance = hCur - hPre; } else { if (stack.size() == 1) { stack.pop(); } distance = A[left] - hPre; } if (distance > 0) { trap = trap + distance * (i - left - 1); } i--; } else if (hCur == hPre && !stack.empty()) { stack.pop(); stack.push(i); } else { stack.push(i); } } return trap; } }
class Solution {
public:
int trap(int A[], int n) {
int left=0,right=0,sum=0,maxhight=0,k=0;
for(int i=0;i<n;i++){ //找到数组中最高的高度
if(A[i]>maxhight){
maxhight=A[i];
k=i;
}
}
for(int i=0;i<k;i++){ //计算最高高度位置左边的水容量大小
if(A[i]<left)sum+=(left-A[i]);
else left=A[i];
}
for(int i=n-1;i>k;i--){ //计算最高高度位置右边的水容量大小
if(A[i]<right)sum+=(right-A[i]);
else right=A[i];
}
return sum;
}
};
import java.util.*; public class Solution { /** * * @param A int整型一维数组 * @return int整型 */ public int trap (int[] A) { //寻找高度最高值的下标 int maxIndex = 0; for(int i = 0; i < A.length; i++){ if(A[i] > A[maxIndex]){ maxIndex = i; } } int sum = 0; //计算最高值的左边储水量 int left = 0; for(int i = 0; i < maxIndex; i++){ if(A[left] > A[i]){ sum += A[left] - A[i]; }else{ left = i; } } //计算最高值右边储水量 int right = A.length - 1; for(int i = A.length - 1; i >= maxIndex; i--){ if(A[right] > A[i]){ sum += A[right] - A[i]; }else{ right = i; } } return sum; } }
看我看我!! 我们可以一层一层的解决问题,从第一次开始,将大于零的都变成1,则两个1之间夹着的0的个数就是这一层的积水量。 然后去掉这一次,检查上面一层。 int trap(int A[], int n) { int *B=new int [n]; int sum=0;//总积水量 while(true){ int location=-1; for(int i=0;i<n;i++){ if(A[i]==0)B[i]=0;//如果是0,不变 else{ B[i]=1;//如果是正数,变成1 if(location>=0)sum+=i-location-1;//location是1的位置 location=i; A[i]-=1;//原来的数组都减去这一层高度 } } if(location==-1)break;//如果location是-1证明全都是0了,每一层都检查完毕。 } delete[]B; return sum; }
public int trap(int[] A) { if(A.length<=2) return 0; int lefttop = A[0], righttop = A[A.length-1]; int i=1, j=A.length-2; int sums = 0; while(i<=j){ if(lefttop>righttop){ if(righttop>=A[j]) sums+= righttop-A[j--]; else righttop = A[j--]; } else{ if(lefttop>=A[i]) sums+= lefttop-A[i++]; else lefttop = A[i++]; } } return sums; }
leetcode最佳答案 class Solution { public: int trap(int A[], int n) { int L_height=0; int r_height=0; int f=0, b=n-1; int res = 0; while(f<=b){ if(L_height<r_height){ res +=max(0, (L_height-A[f])) ; L_height=max(L_height, A[f]); f++; }else{ res += max(0, (r_height-A[b])); r_height=max(r_height, A[b]); b--; } } return res; } };
class Solution { public: int trap(int A[], int n) { int val = 0; int i,j; bool flag = false; for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { if(A[j]>A[i]) break; if(j==n-1 && A[j]<=A[i]) flag = true; } if(flag) break; for(int k=i+1;k<j;k++) { val+=A[i]-A[k]; } i=j-1; } flag = false; for(i=n-1;i>=0;i--) { for(j=i-1;j>=0;j--) { if(A[j]>=A[i]) break; if(j==0 && A[j]<A[i]) flag = true; } if(flag) break; for(int k=i-1;k>j;k--) { val+=A[i]-A[k]; } i=j+1; } return val; } }; /*扫描两遍,一次从前往后,一次从后往前,首先找到第一个比起点值大的位置, 记录此位置,计算起点和此位置之间的容积,然后起点设为记录的位置,继续遍历*/
import java.util.*; public class Solution { public int trap(int[] A) { int n = A.length; int[] maxLeft = new int [n];//找出每个柱子左边最高的 int[] maxRight = new int [n];//找出每个柱子右边最高的 for(int i=1; i<n; i++){ maxLeft[i] = Math.max(maxLeft[i-1], A[i-1]); maxRight[n-1-i] = Math.max(maxRight[n-i], A[n-i]); } int sum = 0; //从左到右找出每个柱子左右最低的部分,再减去当下柱子本身,得出深度 for(int i=1; i<n; i++){ int height = Math.min(maxLeft[i], maxRight[i]); if(height > A[i]){ sum = sum + height - A[i]; } } return sum; } }
/* * Runtime: 22 ms * 参考自leetcode网友:@yuyibestman */ public int trap(int[] height) { if (height == null || height.length < 2) return 0; int leftMax = height[0], rightMax = height[height.length - 1], left = 0, right = height.length - 1; int sum = 0; while (left < right) { leftMax = Math.max(height[left], leftMax); rightMax = Math.max(height[right], rightMax); if (leftMax < rightMax) { sum += leftMax - height[left]; left++; } else { sum += rightMax - height[right]; right--; } } return sum; } /* * 用总面积减去空白面积,再减去边的面积:分别从两侧从中间搜索,找到最高的边停止 runtime:21ms */ public int trap_1(int[] height) { if (height == null || height.length < 2) return 0; int max = height[0]; int sumOfNum = 0; // 记录空白面积 int additionalArea = 0; // 找到最高边和所有边的和 for (int i = 0; i < height.length; i++) { if (max < height[i]) max = height[i]; sumOfNum += height[i]; } int tmpLarge = height[0]; int otherEdge = 0; // 从左边开始搜索 for (int i = 0; i < height.length; i++) { if (tmpLarge < height[i]) { additionalArea += (i - otherEdge) * (max - tmpLarge); otherEdge = i; tmpLarge = height[i]; } // 找到最高边,停止搜索 if (height[i] == max) break; } tmpLarge = height[height.length - 1]; otherEdge = height.length - 1; // 从右边开始搜索 for (int i = height.length - 1; i >= 0; i--) { if (tmpLarge < height[i]) { additionalArea += (otherEdge - i) * (max - tmpLarge); tmpLarge = height[i]; otherEdge = i; } // 找到最高边,停止搜索 if (height[i] == max) break; } int area = height.length * max - sumOfNum - additionalArea; return area; }