Min Stack

2016, Apr 18    

Min Stack

@(算法)[算法, Stack, Zenefits, Uber, Google]

这一题怎样用一句话描述？

实现一个最小栈，不仅能完成栈的各种操作，还能获取当前栈中的最小值。

用到什么算法？什么数据结构？

栈。

通过这题学到了什么？

由于栈是先进后出（FILO）结构，最先进去的元素总是最后出来，某个元素出栈的时间也必然会比后于它入栈的时间晚，所以利用栈的这个特性，我们有以下思路来实现这个“最小栈”：

  1. 首先得有一个“正常”的栈，否则我们无法完成栈的各种操作。
  2. 接着我们用另一个栈，保存当前最小值的信息：栈顶元素永远是当前“正常”栈中所有元素中的最小值。

那么问题来了，第二个栈如何能确保它的栈顶元素，永远是第一个栈中所有元素的最小值呢？

让我们来模拟一下入栈的过程，例如1，2，3顺序入栈，如下图：

push(1)     push(2)     push(3)
|   |       |   |       | 3 |
|   |       | 2 |       | 2 |
| 1 |       | 1 |       | 1 |

人眼一看就知道1是当前最小的元素。但是我们再回过头来看一下1刚入栈，以及2刚入栈时：很显然，这两个阶段1也是当前最小的元素。

那么，我们就可以这样去思考如何实现这个“最小栈”了：如果一个非常小的元素入栈，但是在它后面入栈的元素又比它大，那么“当前最小值”是不会发生改变的；反之，如果一个比较大的元素入栈，但是在它后面入栈的元素一个比一个小，那么“当前最小值”会不断地变小。

所以，以刚才的例子来说，我们的第二个栈就会出现以下入栈序列：

push(1)     push(1)     push(1)
|   |       |   |       | 1 |
|   |       | 1 |       | 1 |
| 1 |       | 1 |       | 1 |

每次第二个栈的入栈元素，都是第一个栈的当前入栈值与第二个栈的栈顶元素（当前最小值）两者之间较小的那一个。

这样，我们每次只要peek第二个栈的栈顶元素就能知道当前最小值了。

如果第一个栈有元素出栈了呢？比如：

pop()       pop()
| 3 |       |   |
| 2 |       | 2 |
| 1 |       | 1 |

那么第二个栈也同时pop就行了，像这样：

pop()       pop()
| 1 |       |   |
| 1 |       | 1 |
| 1 |       | 1 |

剩下来的栈顶元素仍然是“当前最小值”。像这样思考，程序也就不难写出来了。

public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public void push(int number) {
        if (minStack.isEmpty()) {
            minStack.push(number);
        } else {
            minStack.push(Math.min(number, minStack.peek()));
        }
        stack.push(number);
    }

    public int pop() {
        minStack.pop();
        return stack.pop();
    }

    public int min() {
        return minStack.peek();
    }
}

可能(已经)遇到的BUG有？

无。

Twitter Facebook Google+