Save current minimum element's index instead of its value in another stack may reduce memory usage (C++).


  • 2
    E

    Use another stack to save the current minimum element's index instead of its value. In this way, we don't need to change the min stack when push a new element that equals to the minimum element.

    class MinStack
    {
        deque<int> values;
        stack<size_t> minIndexes;
    
    public:
        void push(int x)
        {
            if (minIndexes.empty() || x < getMin())
            {
                minIndexes.emplace(values.size());
            }
    
            values.emplace_back(x);
        }
    
        void pop()
        {
            values.pop_back();
    
            if (minIndexes.top() == values.size())
            {
                minIndexes.pop();
            }
        }
    
        int top()
        {
            return values.back();
        }
    
        int getMin()
        {
            return values[minIndexes.top()];
        }
    };

Log in to reply
 

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