MinStackOPT [source code]

public class MinStackOPT {
static
/******************************************************************************/
public class MinStack {
    long min;
    Stack<Long> stack;

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

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = x;
        } else {
            stack.push(x - min); //Could be negative if min value needs to change
            if (x < min) min = x;
        }
    }

    public void pop() {
        if (stack.isEmpty()) return;        
        long pop = stack.pop();        
        if (pop < 0)  min = min - pop; //If negative, increase the min value        
    }

    public int top() {
        long top = stack.peek();
        if (top > 0) {
            return (int) (top + min);
        } else {
            return (int) (min);
        }
    }

    public int getMin() {
        return (int) min;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MinStackOPT.MinStack minStack = new MinStackOPT.MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin()); //-3
        minStack.pop();
        System.out.println(minStack.top()); //0
        System.out.println(minStack.getMin()); //-2
    }
}

这个是discussion上面的一个最优解, 非常聪明:

作者原话:
The question is ask to construct One stack. So I am using one stack.

The idea is to store the gap between the min value and the current value;

The problem for my solution is the cast. I have no idea to avoid the cast. Since the possible gap between the current value and the min value could be Integer.MAX_VALUE-Integer.MIN_VALUE;

仔细思考一下这个问题, 想知道我这个问题没有做出来到底反映出来我哪些问题;

首先, 做算法题, 最终要追求的一个目的是, 碰到一个完全没有现成模板可以套的题目的时候, 要能冷静的分析面临的困难是什么? 为什么我现在的算法(有时候是笨算法)为什么做不了? 然后你能够根据这个面临的困难, 快速从长期的训练的记忆当中找到合适的应对办法;

纵观这个题目的几个最优解, 其实这个题目本身是一个挺典型的historial stream问题; 当你面临一个pop的时候, 你的困难是, 当你pop掉的是一个min的时候, 你不知道下一个min是什么? 解决这个问题的关键就是怎样保存之前的历史信息; 这个就有点像2sum里面: 当你走到一个数字的时候, 你不知道之前的数字跟这个数字是否有可以组合的.
为了防止后面的(或者说现在的)iteration不知道, 我们在之前的iteration就要存. 这题的核心思想就是这样.
至于具体怎么存, 方法就很多;
最直白的就是wrapper的思路和2stacks的思路. 这两个思路其实都挺中规中矩的, 可惜我一个都没有想到;
当然push min和push gap这两个思路其实就比较难想一点, 但是实际上的本质都是一个store historial information的思路;

另外一个角度: 我们这个题目, 想了这么多, 其实目的就很简单, 就是想要做到O(1)的时间复杂度(指的是某一个operation, 如果是N个operation, 那么我们追求的复杂度其实就是O(N): 处理每一个operation的时间是O(1)), 这个以前也是总结过的, 加速到O(1), 一般的思路也就那么几个. 这里用的就是历史信息处理的方法; 注意, 这里讨论的是加速到O(1), 是指你知道简单的思路无法做到O(1)的情况下, 想要加速, 这个时候你有什么思路;

另外, 这里push gap的思路其实是最优秀的, 因为它要求存储的信息最少;
wrapper and 2stacks其实是每一个value都要对应的存储一个min, 这个其实是没有必要的, 当然维护起来更方便罢了;
push min的思路, 其实space跟上面这俩是差不多的;
只有push gap这个思路, 真正做到了, 只记录the point where min is actually changed.

感觉这个解还是要多酝酿一下, 暂时还是不理解其背后隐含的思考方式;

这个是discussion上面另外一个最优解:

class MinStack  
{  
    static class Element  
    {  
        final int value;  
        final int min;  
        Element(final int value, final int min)  
        {  
            this.value = value;  
            this.min = min;  
        }  
    }  
    final Stack<Element> stack = new Stack<>();  

    public void push(int x) {  
        final int min = (stack.empty()) ? x : Math.min(stack.peek().min, x);  
        stack.push(new Element(x, min));  
    }  

    public void pop()  
    {  
        stack.pop();  
    }  

    public int top()  
    {  
        return stack.peek().value;  
    }  

    public int getMin()  
    {  
        return stack.peek().min;  
    }  
}

没有上面那个slick, 但是想法本身也是很好的, 这里避免计算的手段, 可以理解为类似DP里面的memo;
在data structure的context里来应用这个思想确实也是第一次见到;

Problem Description

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(); .
minStack.pop();
minStack.top();
minStack.getMin(); .
Difficulty:Easy
Total Accepted:132.3K
Total Submissions:468.1K
Contributor: LeetCode
Companies
google uber zenefits amazon snapchat bloomberg
Related Topics
stack design
Similar Questions
Sliding Window Maximum

/**

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