155. 最小栈

Posted on Edited on In , ,
转载自Leet Code

题目描述

设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。

  • push(x)—— 将元素 x 推入栈中。
  • pop()—— 删除栈顶的元素。
  • top()—— 获取栈顶元素。
  • getMin()—— 检索栈中的最小元素。

示例: >输入： >["MinStack","push","push","push","getMin","pop","top","getMin"] >[[],[-2],[0],[-3],[],[],[],[]] >输出： >[null,null,null,null,-3,null,0,-2] >解释： >MinStack minStack = new MinStack(); >minStack.push(-2); >minStack.push(0); >minStack.push(-3); >minStack.getMin(); --> 返回 -3. >minStack.pop(); >minStack.top(); --> 返回 0. >minStack.getMin(); --> 返回 -2.

提示：

  • pop、top和getMin操作总是在非空栈上调用。

我的代码

{.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
43
44
45
46
47
48
49
50
51
52
class MyMinStack {
	
	int min;
	Stack<Integer> stack;

    /** initialize your data structure here. */
    public MyMinStack() 
	{
    	min = Integer.MAX_VALUE;
    	stack = new Stack();
    }
    
    public void push(int x) 
	{
    	stack.push(x);
    	if (x < min) min = x;
    }
    
    public void pop() 
	{
    	int val = stack.pop();
    	if (val == min)
    	{
    		min=Integer.MAX_VALUE;
    		Iterator it = stack.iterator();
    		while(it.hasNext())
    		{
    			int num = (int)it.next();
    			if (num<min) min=num;
    		}
    	}
    }
    
    public int top() 
	{
    	return stack.peek();
    }
    
    public int getMin() 
	{
    	return min;
    }
}

/**
 * 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.getMin();
 */

方法: 辅助栈(以空间换时间)

对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素b, c, d， 那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中， 因为在 a 被弹出之前，b, c, d 不会被弹出。 因此，在操作过程中的任意一个时刻，只要栈顶的元素是a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。 那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。

只需要使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。 因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

  • 当一个元素要入栈时，取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
  • 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；

在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

代码

{.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
43
44
45
46
47
class MinStack155
{
	Stack<Integer> stack;
	Stack<Integer> minStack;
	
	/** initialize your data structure here. */
	public MinStack() 
	{
		stack = new Stack();
		minStack = new Stack();
	}
	
	public void push(int x) 
	{
		if (minStack.isEmpty())
			minStack.push(x);
		else
			minStack.push((minStack.peek()<x)?minStack.peek():x);
		stack.push(x);
	}
	
	public void pop() 
	{
		stack.pop();
		minStack.pop();
	}
	
	public int top() 
	{
		return stack.peek();
	}
	
	public int getMin() 
	{
		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.getMin();
 */