<p>Given <code>n</code> non-negative integers representing an elevation map where the width of each bar is <code>1</code>, compute how much water it can trap after raining.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img src="https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png" style="width: 412px; height: 161px;" />
<pre>
<strong>Input:</strong> height = [0,1,0,2,1,0,1,3,2,1,2,1]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> height = [4,2,0,3,2,5]
<strong>Output:</strong> 9
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == height.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= height[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    int trap(vector<int>& height) {

        // O(N) time and O(N) space
        // two arrays method
        // int n = height.size();
        // if (n == 0) return 0;
        
        // vector<int> left(n);
        // vector<int> right(n);
        
        // // Fill left array
        // left[0] = height[0];
        // for (int i = 1; i < n; i++) {
        //     left[i] = max(left[i - 1], height[i]);
        // }
        
        // // Fill right array
        // right[n - 1] = height[n - 1];
        // for (int i = n - 2; i >= 0; i--) {
        //     right[i] = max(right[i + 1], height[i]);
        // }
        
        // // Calculate trapped water
        // int trappedWater = 0;
        // for (int i = 0; i < n; i++) {
        //     trappedWater += min(left[i], right[i]) - height[i];
        // }
        
        // return trappedWater;




        // O(N) time and O(1) space
        // Two pointers 
        // int left = 0;
        // int right = height.size() - 1;
        // int leftMax = height[left];
        // int rightMax = height[right];
        // int water = 0;

        // while (left < right) {
        //     if (leftMax < rightMax) {
        //         left++;
        //         leftMax = max(leftMax, height[left]);
        //         water += leftMax - height[left];
        //     } else {
        //         right--;
        //         rightMax = max(rightMax, height[right]);
        //         water += rightMax - height[right];
        //     }
        // }

        // return water;
        int n = height.size();
        int ans = 0;
        for (int i = 0; i < n - 2;) {
            int max = 0;
            int temp = 0;
            int j = i + 1;
            while (j < n) {
                if (height[j] >= height[i]) {
                    ans += ((j - i - 1) * height[i]) - temp;
                    i = j;
                    break;
                }
                else if (max == 0 || height[j] > height[max]) {
                    max = j;
                }
                temp += height[j++];
            }
            if (j == n) {
                temp = 0;
                for (int k = i + 1; k < max; k++) {
                    temp += height[k];
                }
                ans += ((max - i - 1) * height[max]) - temp;
                i = max;
            }

        }
        return ans;
    }
};
24800