Given_n_non-negative integers representing an elevation map where the width of each bar is1
, compute how much water it is able to trap after raining.
Have you met this question in a real interview?
Yes
Example
Given[0,1,0,2,1,0,1,3,2,1,2,1]
, return6
.
O(n) time and O(1) memory
O(n) time and O(n) memory is also acceptable.
class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
// write your code here
int res = 0;
if (heights.empty()) {
return 0;
}
int left = 0, right = heights.size() - 1;
int l = heights[left];
int r = heights[right];
while (left < right) {
if (l < r) {
++left;
res += max(l - heights[left], 0);
l = max(l, heights[left]);
} else {
--right;
res += max(r - heights[right], 0);
r = max(r, heights[right]);
}
}
return res;
}
};
class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
// write your code here
int water = 0;
if (heights.size() < 3) {
return 0;
}
vector<int> leftHeight(heights.size(), 0);
vector<int> rightHeight(heights.size(), 0);
leftHeight[0] = heights[0];
for (int i = 1; i < heights.size(); ++i) {
leftHeight[i] = max(leftHeight[i-1], heights[i]);
}
rightHeight[heights.size()-1] = heights[heights.size()-1];
for (int j = heights.size()-2; j >= 0; --j) {
rightHeight[j] = max(rightHeight[j+1], heights[j]);
}
for (int i = 1; i < heights.size(); ++i) {
water += min(leftHeight[i], rightHeight[i]) - heights[i];
}
return water;
}
};
class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
// write your code here
int left = 0, right = heights.size()-1;
int water = 0;
int smaller = 0;
while (left < right) {
if (heights[left] < heights[right]) {
smaller = heights[left];
while (left < right && heights[left] <= smaller) {
water += smaller - heights[left];
++left;
}
} else {
smaller = heights[right];
while (left < right && heights[right] <= smaller) {
water += smaller - heights[right];
--right;
}
}
}
return water;
}
};
class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
// write your code here
int res = 0;
if (heights.empty()) {
return 0;
}
int left = 0, right = heights.size() - 1;
int l = heights[left];
int r = heights[right];
while (left < right) {
if (l < r) {
++left;
if (heights[left] < l) {
res += l - heights[left];
} else {
l = heights[left];
}
} else {
--right;
if (heights[right] < r) {
res += r - heights[right];
} else {
r = heights[right];
}
}
}
return res;
}
};