LeetCode 155 Min Stack

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，pop，top，和取最小值。

push(x) – 元素x压入栈
pop() – 弹出栈顶元素
top() – 获取栈顶元素
getMin() – 获取栈中的最小值

解题思路：

这是考察Algorithm和data structure的经典问题。用stack即可实现push，top，pop。难点在于O(1)内实现getMin。看一个例子，
按以下顺序加入stack 5, 3, 6, 8, 2
最小值 5, 3, 3, 3, 2
可以看出来，最小值是动态变化的，所以需要动态处理，由于存储的方式与stack一致，所以可以考虑再用一个stack来存最小值。
如果不用额外stack改用Node，将make_pair(x, curMin)一起压入栈stack>中，额外空间复杂度O(n)。见算法2。
稍改进空间复杂度，最小值只存变化的值，也就是5,3,2，当最小值变化时再存入最小栈。出栈时候，若出栈元素等于最小栈中的元素，
最小栈的元素也要出栈。

注意事项：

当前最小元素可能相等。相等元素也要入最小栈，如5,3,6,3，最小栈为5,3,3。val <= self.min_stack[-1]一定要取等于。
考虑栈为空时，执行pop和peek的操作。这里存在一个decision point，设计原则与stack的操作一致，也就是暴露出exception。

Python代码：

class MinStack(TestCases):

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        self.stack.append(val)

    def pop(self) -> None:
        val = self.stack.pop()
        if self.min_stack and val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

注意事项：

当前最小元素可能相等。相等元素也要入最小栈，如5,3,6,3，最小栈为5,3,3。x <= minS.peek()一定要取等于。
考虑栈为空时，执行pop和peek的操作。这里存在一个decision point，设计原则与stack的操作一致，也就是暴露出exception。

Java代码：

public class MinStack {

	 /** initialize your data structure here. */
    public MinStack() {
        s = new Stack<>();
        minS = new Stack<>();
    }
    
    public void push(int x) {
        s.push(x);
        
        if(minS.isEmpty() || x <= minS.peek())
        	minS.push(x);
    }
    
    public void pop() {
        int top = s.pop();
        if(top == minS.peek())
        	minS.pop();
    }
    
    public int top() {
        return s.peek();
    }
    
    public int getMin() {
        return minS.peek();
    }
    
    Stack<Integer> s;
    Stack<Integer> minS;
}

O(1)空间算法分析(不用看)：

时间复杂度为O(1)，空间复杂度O(n)。

算法2也是可以通过leetcode测试的，虽然空间复杂度比上述差。
存储每个新加值对应的min，更加浪费空间

Follow-up:

如果用O(1)额外空间，怎么改进算法？

先考虑最简单的情况，用一个min来记录当前最小值，它可以满足最小值不需更新的情况，解决了问题的一半：
x表示要加入的值，m表示最小值的变量，y是真正加入栈的值
x 1 5 3
m 1 1 1
y 1 5 3
可以看出无论入栈出栈，最小值均为1.

比较难的是最小值需要更新时，如下一个要加入0，最小值要更新m=0，但0不能入栈，前一个最小值1的信息就丢失了，所以要设计一个计算y方法(push)满足

已知条件：含有前一个最小值的的信息。x1<m0.
设计要求：y<m, 因为最小值不更新的时候y值永远大于等于m，必须区分开来，从而知道怎么pop，也就是还原入栈值（最小值）。y1<m1=x1.
解决了这个问题就解决了另一半的问题。

以下解释如何推出最小值需要更新时y的计算方式（，以及push和pop的方法：

以下例子解释Push
x 1 5 3 0 6
m 1 1 1 0 0
y 1 5 3 -1 6

以下例子解释Pop
x 6 0 3 5 1
m 0 0 1 1 1
y 6 -1 3 5 1
可以看出真正入栈值可以是原数或者是计算值，取决它与最小值的关系。

注意事项：

当前最小元素可能相等。相等元素不用更新最小值，也就是新值直接入栈。
以上递推式的初始条件为：第一个元素是直接加入栈且等于m，无论何种情况都不需任何计算。push时候注意当栈为空，m值为第一个元素的值。
数据溢出。涉及int的加减乘除法，都要预先将其转化为long，否则会溢出。

Java代码：

public class MinStack {
     public MinStack() {
        s = new Stack<>();
    }
    
    public void push(int x) {
    	if (s.isEmpty())
    		m = x;
    	
    	long xx = (long)x;
    	if (x >= m)
    		s.push(xx);
    	else {
    		s.push(2*xx-m);
    		m = x;
    	}
    }
    
    public void pop() {
        long top = s.pop();
        if(top < m)     
        	m = 2*m - top;
    }
    
    public int top() {
        return (int)(s.peek() >= m? s.peek() : m);
    }
    
    public int getMin() { 
        return (int)m;
    }
    
    Stack<Long> s;
    long m = 0;
}

算法分析：

时间复杂度为O(1)，空间复杂度O(1)。

考点:

先不考虑getMin，用什么数据结构实现push, pop, top
暴力法可以实现getMin，怎么实现O(1)。用什么数据结构实现存储min，额外用一个stack
元素可能相等
考虑栈为空时，执行pop和peek的操作