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

Posted on Edited on In , ,
转载自Leet Code《剑指Offer》

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.

提示：

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

我的思路

考虑在普通栈之外增加一个辅助栈minStack来实现。 思路是，普通栈stack的每个元素都对应一个存储在minStack中的当前最小值。 在调用min()函数时，只需要查看当前stack的栈顶对应的minStack的栈顶即可。 即，牺牲空间来换取\(O(1)\)的时间。

首先考虑新元素入栈push(x)。 对于普通栈stack，此时无论如何都正常入栈。 对于辅助栈minStack，当minStack为空时，表示目前没有备选的min，因此将其入栈minStack。 而当minStack不为空时，如果其栈顶peek大于新元素x，则说明此处 (stack的栈顶x处) 对应的最小值应该是x，因此也将其入栈minStack。 但是，当minStack的栈顶peek小于新元素x时，说明此处 (stack的栈顶x处) 对应的最小值还是peek而不是新元素x。因此minStack中入栈的还是自己的栈顶。

接下来考虑出栈pop()。 由于普通栈stack和辅助栈minStack中的元素一一对应，因此出栈时两个栈都要进行弹出操作。

最后，取栈顶top()时看普通栈stack，取最小值min()时看辅助栈minStack即可。

我的代码

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MyMinStack {
	Stack<Integer> stack;
	Stack<Integer> minStack;

    /** initialize your data structure here. */
    public MyMinStack() {
    	stack = new Stack();
    	minStack  = new Stack();
    }
    
    public void push(int x) {
    	
    	if (minStack.isEmpty()||minStack.peek()>x) 
            minStack.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();
 */