题目

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

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：

各函数的调用总次数不超过 20000 次

解题思路

使用List类来实现min栈的功能：

push：调用add函数直接插入

pop：调用remove删除最后一位的数

top：调用get获取最后一位的数

min：使用Collections自带的min获取集合的最小值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MinStack {

    /** initialize your data structure here. */
    List<Integer> list ;
    public MinStack() {
        list=new ArrayList<Integer>();
    }
    
    public void push(int x) {
        list.add(x);
    }
    
    public void pop() {
        list.remove(list.size()-1);
    }
    
    public int top() {
       return list.get(list.size()-1);
    }
    
    public int min() {
        return Collections.min(list);
    }
}

官方题解

函数设计：
push(x) 函数：重点为保持栈B的元素是非严格降序的。

  • 将x压入栈 A （即 A.add(x) ）；

  • 若 ① 栈B为空 或 ② x小于等于栈B的栈顶元素，则将x压入栈B （即 B.add(x) ）。

pop() 函数：重点为保持栈 A，B 的元素一致性 。

  • 执行栈 A 出栈（即 A.pop() ），将出栈元素记为 y ；
  • 若 y等于栈 B 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）。

top() 函数：直接返回栈A的栈顶元素即可，即返回 A.peek() 。

min() 函数：直接返回栈B的栈顶元素即可，即返回 B.peek() 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}