why push x again if x == getMin()?? use index/offset instead!!


  • 0
    Q
    class MinStack { // do not update stack for min if x == getMin() when do push.
    public:
        typedef int T;
        /** initialize your data structure here. */
        MinStack() : stack{}, pmin_stack{} {
        }
        void push(int x) {
            bool need_to_update_pmin = (stack.empty() || getMin() > x);
            if (need_to_update_pmin) { pmin_stack.push_back(stack.size()); }
            stack.push_back(x);
        }
        
        void pop() {
            stack.pop_back();
            bool need_to_update_pmin = (stack.size() == pmin_stack.back());
            if (need_to_update_pmin) { pmin_stack.pop_back(); }
        }
        
        int top() {
            return stack.back();
        }
        
        int getMin() {
            return stack[pmin_stack.back()];
        }
    private:
        std::vector<T> stack;
        vector<size_t> pmin_stack;
    };

Log in to reply
 

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