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.
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 = 0, mx = 0, n = heights.size(); vector<int> dp(n, 0); for (int i = 0; i < n; ++i) { dp[i] = mx; mx = max(mx, heights[i]); } mx = 0; for (int i = n - 1; i >= 0; --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 = 0, l = 0, r = heights.size() - 1; 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 = 0, l = 0, r = heights.size() - 1, level = 0; while (l < r) { int lower = heights[(heights[l] < heights[r]) ? l++ : r--]; level = max(level, lower); res += level - lower; } return res; } };
本文转自博客园Grandyang的博客，原文链接： 收集雨水[LintCode] Trapping Rain Water，如需转载请自行联系原博主。
