30 包含 min 函数的栈

leetcode-cn

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3); minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.

class MinStack {
    Deque<Integer> stack;
    Deque<Integer> min;

    /** initialize your data structure here. */
    public MinStack() {
        stack=new LinkedList<>();
        min=new LinkedList<>();
    }
    
    public void push(int x) {
        stack.push(x);
        if(min.isEmpty() || min.peek()>x){
            min.push(x);
        } else {
            min.push(min.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        min.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return min.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();
 */

牛客

描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素

使用 2 个栈，一个是普通的栈，一个是存最小值的栈，栈顶表示当前最小值。当压入时，如果新值小于最小值，压入新值，否则压入最小值。弹出时两个栈同时弹出。

public class Solution {

    Deque<Integer> stack = new LinkedList<Integer>();
    Deque<Integer> min = new LinkedList<Integer>();
    
    public void push(int node) {
        stack.push(node);
        if(min.size()>0 && min.peek()<node){
            min.push(min.peek());
        } else {
            min.push(node);
        }
    }
    
    public void pop() {
        stack.pop();
        min.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return min.peek();
    }
}

java.util.Stack 是一个类，栈应该作为一种接口，而且 Stack 底层是数组，栈不需要随机访问，用链表更合适。因此不推荐使用 Stack ，推荐用 java.util.Deque 代替，实现类可以使用 LinkedList

Deque 接口文档：

Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class. When a deque is used as a stack, elements are pushed and popped from the beginning of the deque. Stack methods are precisely equivalent to Deque methods as indicated in the table below:
Comparison of Stack and Deque methods
Stack Method
Equivalent Deque Method
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()