Skip to content

Instantly share code, notes, and snippets.

@vitkarpov
Created November 6, 2019 12:08
Show Gist options
  • Save vitkarpov/f96edaefb1512bae2a64ad395f35dc6d to your computer and use it in GitHub Desktop.
Save vitkarpov/f96edaefb1512bae2a64ad395f35dc6d to your computer and use it in GitHub Desktop.
Trapping Rain Water (Dynamic Programming)
class Solution {
public:
int trap(const vector<int>& h) {
int n = h.size();
vector<int> left_max(n + 1);
vector<int> right_max(n + 1);
for (int i = 1; i <= n; i++) {
left_max[i] = max(left_max[i - 1], h[i - 1]);
}
for (int i = n - 2; i >= 0; i--) {
right_max[i] = max(right_max[i + 1], h[i + 1]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += max(0, min(left_max[i], right_max[i]) - h[i]);
}
return ans;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment