Shortest and fastest 1-stack and 2-stack solutions


  • 10
    L

    2-stack solution may use less memory (ironically) since we don't save the 'min' for every pushed element.
    If there are a lot of repeated elements, we may save even more memory by introducing a 'count' for each 'min'.

    Cannot use vector (will get memory limit error), as vector doubles its capacity when full, whereas deque has a better capacity management strategy.

    2 deque:

        deque<int> stack;
        deque<int> mins;
        
        void push(int x) {
            int themin = mins.size() ? mins.back() : x;
            stack.push_back(x);
            if (x<=themin)
                mins.push_back(x);
        }
    
        void pop() {
            if (stack.back()==mins.back())
                mins.pop_back();
            stack.pop_back();
        }
    
        int top() {
            return stack.back();
        }
    
        int getMin() {
            return mins.back();
        }
    

    1 deque (save current min for every pushed elem):

    typedef pair<int,int> pairt;
    
        deque<pairt> stack;
    
        void push(int x) {
            if (stack.size())
                stack.push_back(make_pair(x, min(x,getMin()) ));
            else 
                stack.push_back(make_pair(x, x));
        }
    
        void pop() {
            stack.pop_back();
        }
    
        int top() {
            return stack.back().first;
        }
    
        int getMin() {
            return stack.back().second;
        }

  • 0
    J

    I like this more than other solutions! Thanks for sharing!


  • 0
    L

    I got MLE for the 1-deque solution. I think it almost doubles the memory.


  • 0
    Y

    I agree.1-deque solution wastes the momory.


Log in to reply
 

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