155. Min Stack
今天遇到一个不一样的 leetcode
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
这个题有一个关键的点: 当前入栈的元素和当前的极值的关系需要用栈来存储。用一个变量可以存储极值，那么栈顶就可以用来存储差值。
两个关键的信息存储的点：
- 最小值亦是
- 堆顶元素
我们来看一个例子：
push: 1 3 0 1 8
| min | stack push | stack pop |
|---|---|---|
| 1 | 1 - 1 = 0 | - |
| - | 3 - min = 2 | - |
| - | 0 - min = -1 | - |
| 0 | 1 - min = 1 | - |
| - | 8 - min = 8 | - |
pop
| min | stack push | stack pop(from bottom to top) | min(from bottom to top) |
|---|---|---|---|
| 1 | 1 - 1 = 0 | 0 + min = 1 | - |
| - | 3 - min = 2 | 2 + min = 3 | - |
| - | 0 - min = -1 | -1 < 0, min | min - (0 - pre_min) = 0 - ( 0 - 1) = 1 |
| 0 | 1 - min = 1 | 1 + min = 1 | - |
| - | 8 - min = 8 | 8 + min = 8 | 0 |
为什么再次遇见更小的值的时候，不能存储 0 到栈顶来表示？
- cur_min - cur_min 不能记录 pre_min 的值
- 没有符号变化，就无法判断 cur_min 是否变更