l********o
发帖数: 56 | 1 Leetcode原题Trapping Rain Water，要求算法复杂度O(N), 只能用两个不套在一起的
for loop，只能开辟O(1)额外的空间.
Houzz的题。会做的朋友能帮忙说一下么？ | D*********S
发帖数: 21 | 2 其实还能再优化一点，只不过加的限制条件太怪了，“只能用两个不套在一起的
下面给的相当于就一个for loop, one pass time O(n), space O(1)
class Solution {
public:
int trap(const vector& h) {
const int sz=h.size();
if(sz<=2)
return 0;
int leftMax=h[0], rightMax=h[sz-1], left=1, right=sz-2, ret=0;
while(left<=right)
if(leftMax
{
if(h[left]
ret+=leftMax-h[left];
else
leftMax=h[left];
++left;
}else
{
if(h[right]
ret+=rightMax-h[right];
else
rightMax=h[right];
--right;
}
return ret;
}
}; | M***6
发帖数: 895 | 3 先扫一遍找到array的max值，然后从左0往右扫到max算有多少雨水，然后再从右边
length －1往左到max，算有多少雨水。。算每个bin上有多少水用stack的思想，但是
不用需要stack。。
比如算左到右：
int pre = -1;
int i = 0;
while(i < maxIndex){
if(height[i] < pre){
sum += (pre - height[i]);
}
else{
pre = height[i];
}
i++;
} |
|
