LeetCode155（最小栈）

发表于 | 分类于 ，

题目：

　　设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
　　push(x) – 将元素 x 推入栈中。
　　pop() – 删除栈顶的元素。
　　top() – 获取栈顶元素。
　　getMin() – 检索栈中的最小元素。

思路：

　　需要维护一个辅助栈，使该辅助栈的栈顶元素保持为栈的最小元素。

代码：

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
class MinStack {
	Deque<Integer> stack1;
	Deque<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
    
    public void push(int x) {
        stack1.push(x);
        if (stack2.isEmpty()) {
			stack2.push(x);
		}else if (stack2.peek() < x) {
			stack2.push(stack2.peek());
		}else {
			stack2.push(x);
		}
    }
    
    public void pop() {
    	// 最好加入空指针处理
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int getMin() {
        return stack2.peek();
    }
}

复杂度分析及总结：

　　时间复杂度：
　　　　O(1)。
　　空间复杂度：
　　　　O(n)。辅助栈需要大小为n的空间。