剑指 Offer 30. 包含min函数的栈(Sword finger offer 30 Stack containing min function)

剑指 Offer 30. 包含min函数的栈

class MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int x) {
        if(minStack.isEmpty()) {
            stack.push(x);
            minStack.push(x);
        } else {
            if (x < minStack.peek()) {
                minStack.push(x);
                stack.push(x);
            } else {
                minStack.push(minStack.peek());
                stack.push(x);
            }
        }
    }
    
    public void pop() {
        minStack.pop();
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

利用一个栈也可以,不过可以往栈中存储一个结点\(node\),保存有当前的值和当前的最小值两个元素。

class MinStack {
    private static class Node {
        private int val;
        private int currMin;
        public Node() {

        }
        public Node(int val, int currMin) {
            this.val = val;
            this.currMin = currMin;
        }
    }
    private Deque<Node> stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new ArrayDeque<>();
    }
    
    public void push(int x) {
        if(stack.isEmpty()) {
            Node node = new Node(x, x);
            stack.push(node);
        } else {
            if (x < stack.peek().currMin) {
                Node node = new Node(x, x);
                stack.push(node);
            } else {
                Node node = new Node(x, stack.peek().currMin);
                stack.push(node);
            }
        }
    }
    
    public void pop() {
        stack.pop();
    }   
    
    public int top() {
        return stack.peek().val;
    }
    
    public int min() {
        return stack.peek().currMin;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */
————————

Sword finger offer 30 Stack containing min function

class MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int x) {
        if(minStack.isEmpty()) {
            stack.push(x);
            minStack.push(x);
        } else {
            if (x < minStack.peek()) {
                minStack.push(x);
                stack.push(x);
            } else {
                minStack.push(minStack.peek());
                stack.push(x);
            }
        }
    }
    
    public void pop() {
        minStack.pop();
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

You can also use a stack, but you can store a node \ (node \) in the stack, which contains two elements: the current value and the current minimum value.

class MinStack {
    private static class Node {
        private int val;
        private int currMin;
        public Node() {

        }
        public Node(int val, int currMin) {
            this.val = val;
            this.currMin = currMin;
        }
    }
    private Deque<Node> stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new ArrayDeque<>();
    }
    
    public void push(int x) {
        if(stack.isEmpty()) {
            Node node = new Node(x, x);
            stack.push(node);
        } else {
            if (x < stack.peek().currMin) {
                Node node = new Node(x, x);
                stack.push(node);
            } else {
                Node node = new Node(x, stack.peek().currMin);
                stack.push(node);
            }
        }
    }
    
    public void pop() {
        stack.pop();
    }   
    
    public int top() {
        return stack.peek().val;
    }
    
    public int min() {
        return stack.peek().currMin;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */