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

        if(height.empty()) return 0;

        int n = (int)height.size();
        vector<int>pre(n, -1);
        vector<int>suf(n, -1);

        pre[0] = 0;
        for(int i=1;i<n;i++)
        {
            pre[i] = max(pre[i-1], height[i-1]);
        }

        suf[n-1] = 0;
        for(int i=n-2;i>=0;i--)
        {
            suf[i] = max(suf[i+1], height[i+1]);
        }

        int ans = 0;


        for(int i=1;i<n-1;i++)
        {
            int mn = min(suf[i], pre[i]);

            if(mn == 0 )continue;
            if(mn > height[i])
            ans += mn - height[i];
        }

        return ans;

    }
};