<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>& arr){
    //     int i=0;
    //     int j =arr.size()-1;
    //     int lm=0;
    //     int rm=0;
    //     int total=0;
    //    while(i<j){
    //     if(arr[i]<=arr[j]){
    //         if(lm>arr[i]){
    //             total+=lm-arr[i];
    //         }
    //         else{
    //             lm=arr[i];
    //         }
    //         i++;
    //     }
    //     else{
    //         if(rm>arr[j]){
    //             total+=rm-arr[j];
    //         }
    //         else{
    //             rm=arr[j];
    //         }
    //         j--;
    //     }
    //    } 
    //    return total;
    // }
    int trap(vector<int>& height) {
        vector<int> suffixm(height.size());
        for(int i=height.size()-1;i>=0;i--){
            if(i<height.size()-1){
                suffixm[i]=max(suffixm[i+1],height[i]);
            }
            else{
                suffixm[i]=height[i];
            }
        }
        int total=0;
        int lmx;
        for(int i=0;i<height.size();i++){
            if(i>0){
                lmx=max(lmx,height[i-1]);
            }
            else{
                lmx=height[i];
            }
            cout<<lmx<<" ";
            if((height[i]<lmx) && (height[i]<suffixm[i])){
                total+=min(lmx,suffixm[i])-height[i];
            }
        }
        return total;
    }
};
25200