My concise code (20ms, stack based, O(n)), one trick used


  • 35
    D

    The idea is simple, use a stack to save the index of each vector entry in a ascending order; once the current entry is smaller than the one with the index s.top(), then that means the rectangle with the height height[s.top()] ends at the current position, so calculate its area and update the maximum.
    The only trick I use to avoid checking whether the stack is empty (due to pop) and also avoiding emptying the stack at the end (i.e. after going through the vector, s is not empty and we have to consider those in the stack) is to put a dummy "0" at the beginning of vector "height" and the end of "height": the first one makes sure the stack will never be empty (since all the height entries are >=0) and the last one will flush all the remaining non-zero entries of the stack at the end of "for" iteration. This trick helps us keep the code concise.

    class Solution {
    public:
        int largestRectangleArea(vector<int>& height) {
            height.insert(height.begin(),0); // dummy "0" added to make sure stack s will never be empty
            height.push_back(0); // dummy "0" added to clear the stack at the end
            int len = height.size();
            int i, res = 0, idx;
            stack<int> s; // stack to save "height" index
            s.push(0); // index to the first dummy "0"
            for(i=1;i<len;i++)
            {
                while(height[i]<height[idx = s.top()]) // if the current entry is out of order
                {
                    s.pop();
                    res = max(res, height[idx] * (i-s.top()-1) ); // note how the width is calculated, use the previous index entry
                }
                s.push(i);
            }
            height.erase(height.begin()); // remove two dummy "0"
            height.pop_back();
            return res;
        }
    };

  • 1
    H

    I have tried several times for this trick, the run time is still 24 ms. Maybe stack empty check is not expensive comparing to stack top call. But code becomes more concise. Good trick.


  • 0
    F

    This solution didn't check the edge case. The rectangular with height of the minimum height and spans all the width.


  • 0
    D

    Thanks for your comment. I believe that "height.push_back(0); " was supposed to do the trick. You may want to try severak test cases to see how it works.


  • 0
    F

    Oh, right, sorry, I forget these two dummy 0s in the front and end. Yes, this should work, and quite elegant trick. Thanks for providing this solution !


  • 0
    R

    I did not get it. what do you mean by rectangle finish here? maybe some height afterwards, can make a bigger rectangle with this one, why do you pop(), when you pop() why do you compute the width as in the code with the element before the previous top element of the stack? the whole algorithm is not well-explained


  • 0
    A

    why do you need to push 0 before? If start i=0, emplace(0), why it causes run time error?


  • 0
    H

    "dummy "0" added to make sure stack s will never be empty" is bright


  • 0
    This post is deleted!

Log in to reply
 

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