Skip to content

Instantly share code, notes, and snippets.

@vitkarpov

vitkarpov/trapping-water.cpp

Created October 29, 2019 16:26
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save vitkarpov/8e355ee24e9bd5b740f84a411f01df43 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save vitkarpov/8e355ee24e9bd5b740f84a411f01df43 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. vitkarpov created this gist Oct 29, 2019.
    20 changes: 20 additions & 0 deletions trapping-water.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,20 @@
    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;
    }
    };