[LintCode] Trapping Rain Water 收集雨水

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

[LintCode] Trapping Rain Water 收集雨水

Have you met this question in a real interview?
Yes
Example

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Challenge

O(n) time and O(1) memory

O(n) time and O(n) memory is also acceptable.

LeetCode上的原题,请参见我之前的博客Trapping Rain Water

解法一:

class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
int res = , mx = , n = heights.size();
vector<int> dp(n, );
for (int i = ; i < n; ++i) {
dp[i] = mx;
mx = max(mx, heights[i]);
}
mx = ;
for (int i = n - ; i >= ; --i) {
dp[i] = min(dp[i], mx);
mx = max(mx, heights[i]);
if (dp[i] > heights[i]) res += dp[i] - heights[i];
}
return res;
}
};

解法二:

class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
int res = , l = , r = heights.size() - ;
while (l < r) {
int mn = min(heights[l], heights[r]);
if (mn == heights[l]) {
++l;
while (l < r && heights[l] < mn) {
res += mn - heights[l++];
}
} else {
--r;
while (l < r && heights[r] < mn) {
res += mn - heights[r--];
}
}
}
return res;
}
};

解法三:

class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
int res = , l = , r = heights.size() - , level = ;
while (l < r) {
int lower = heights[(heights[l] < heights[r]) ? l++ : r--];
level = max(level, lower);
res += level - lower;
}
return res;
}
};
上一篇:Hibernate: org.hibernate.exception.SQLGrammarException: could not insert: 错误


下一篇:CAM(Content Addressable Memory)介绍