11ms, my clean c++, O(n)


  • 1
    L
    class Solution {
    public:
        int trap(vector<int>& height) {
            int L = height.size();
            int p = 0;
            int q = L - 1;
            int total = 0;
            int trap_height = 0;
            while(p < q) {
                trap_height = min(height[p], height[q]);
                while(p < q && height[p] <= trap_height) {
                    p++;
                    total += max(0, trap_height - height[p]);
                }
                while(q > p && height[q] <= trap_height) {
                    q--;
                    total += max(0, trap_height - height[q]);
                }
            }
            return total;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.