My stack based O(n) solution


  • 1
    A

    The idea is enlightened by the hist area solution.
    The stack always store bars greater than the current bar.
    If the current bar is greater than the top of the stack, that means we may can keep some water now.
    So we pop the stack to see if there is a bar forehead can keep some water with the current bar.
    It should be noted that: if this happens, that means the water lower than 'this level' has been accounted. Therefore, we should only account water above this level when we consider the next forehead bar.
    So we have water = ( min( A[ stBars.top() ], A[ i ]) - A[ tp ]) * ( i - stBars.top() - 1 );
    Another observation is that a bar cannot keep water with something out of the range. So water=0 when the stack is empty. And we do not need to consider the bars remaining in the stack when A is scanned over.

    class Solution {
    public:
        int trap(int A[], int n) {
        if( n <= 0 ) return 0;
        int ans = 0;
        int i = 0;
        stack<int> stBars;
        while( i < n )
        {
            if( stBars.empty() || A[ i ] <= A[ stBars.top()])
            {
                stBars.push( i++ );
            }
            else
            {
                int tp = stBars.top();
                while( !stBars.empty() && A[ tp ] < A[ i ])
                {
                    stBars.pop();
                    int water = 0;
                    if( !stBars.empty() )
                    {
                        water = ( min( A[ stBars.top() ], A[ i ]) - A[ tp ]) * ( i - stBars.top() - 1 );
                        tp = stBars.top();
                    }
                    ans += water;
                }
            }
        }
        return ans;
        }
    };

  • 0

    Could you indent your code properly by highlighting your code and clicking on the {} button?


  • 0
    A

    Sorry. I'm not familiar with the editor. Done now.


Log in to reply
 

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