Beats 80% Java Solution. All of stack operations use O(1) time.


  • 0
    F

    Just hold current min value in each node.

    public class MinStack {
            public static class StackNode {
                public int getVal() {
                    return val;
                }
    
                public void setVal(int val) {
                    this.val = val;
                }
    
                public int getMinVal() {
                    return minVal;
                }
    
                public void setMinVal(int minVal) {
                    this.minVal = minVal;
                }
    
                public StackNode(int val, int minVal) {
                    this.val = val;
                    this.minVal = minVal;
                }
    
                private int val;
                private int minVal;
            }
    
            private Deque<StackNode> stack ;
    
            /** initialize your data structure here. */
            public MinStack() {
                stack = new ArrayDeque<>();
            }
    
            public void push(int x) {
                StackNode topNode = stack.peek();
                if (topNode == null) {
                    StackNode node = new StackNode(x, x);
                    stack.push(node);
                } else {
                    int minVal = topNode.getMinVal();
                    int newMinValue = minVal;
                    if (x < minVal) {
                        newMinValue = x;
                    }
                    StackNode node = new StackNode(x, newMinValue);
                    stack.push(node);
                }
            }
    
            public void pop() {
                stack.pop();
            }
    
            public int top() {
                if (stack.isEmpty()) {
                    return 0;//?
                }else {
                    return stack.peek().getVal();
                }
            }
    
            public int getMin() {
                if (stack.isEmpty()) {
                    return 0; // ?
                } else {
                    return stack.peek().getMinVal();
                }
            }
    }
    

Log in to reply
 

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