Trapping Rain Water (Dynamic Programming)

trapping-rain-water.cpp

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;
  }
};