[C++] Clean Code


  • 2

    Term

    Extensible - bucket with a height start from here or earlier, and could still be extended further in the row.
    

    Idea

    • Keep an ever increasing stack of all the bucket that is not terminated currently.
    • Whenever meet a shorter bucket, pop all the hopeless bucket on the stack that is taller, which will be terminated by this decreasing bucket.
    • The end (to) bucket is i(current), and the start bucket is the stack.top() + 1. (Not necessarily the popped bucket, because it kicked those hopeless bucket that were taller than it, until the first shorter bucket on the stack. That's why we keep an ever increasing stack).
    • All bucket will be push to stack when every shorter bucket on stack is kicked out. And they will be kept on the stack for as long as there is no shorter bucket to break their extensibility.
        /**
         *                       _
         *                   _  | |
         *               _  |_|_|_|
         *           _  |_|_|___|_|
         *       _  |_|_|___|___|_|
         *      |_|_|___|___|___|_|
         *      |___|___|___|___|_|_
         * i: -1 0 1 2 3 4 5 6 7 8 9 
         * 
         * h:    2 1 3 2 4 3 5 4 6(0)
         * 
         * s:    0 1 1 1 1 1 1 1 1 (stack actually save index, but to make it clear, here we shows the actual height on that index)
         *           3 2 2 2 2 2 2
         *               4 3 3 3 3
         *                   5 4 4
         *                       6
         */
    
    class Solution {
    public:     
        int largestRectangleArea(vector<int>& h) {
            stack<int> s;       // stack of every increasing buckets
            h.push_back(0);     // the ultimate terminator
    
            int maxrect = 0;
            for (int i = 0; i < h.size(); i++) {
                while (!s.empty() && h[s.top()] > h[i]) {
                    int height = h[s.top()];
                    s.pop();
                    int left = !s.empty() ? s.top() + 1 : 0;    // left is 0 or s.top()+1, not popped bucket, could be tallers not in stack
                    maxrect = max(maxrect, height * (i - left));
                }
                s.push(i);  // eventually push i, after all hopeless buckets taller than h[i] kicked out;
            }
            return maxrect;
        }
    };
    

Log in to reply
 

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