最小栈-Min Stack-leetcode

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

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

示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

思路：

1. 链式栈：
   使用两个链式栈stack，minStack ；stack正常的出栈和入栈；当stack入栈x的时候和minstack栈顶比较，如果入栈的值比minstack小，就把x在minstack中进行入栈，所以minstack保存的是较小的值；
   出栈操作：stack出栈，使用栈顶元素与minstack栈顶值比较，如果大于minstack的栈顶值就可以判断stack的最小值为minstack栈顶值；反之。

public class MinStack {
    private Stack<int> stack = new Stack<int>();
    private Stack<int> minStack = new Stack<int>();
    
    /** initialize your data structure here. */
    public MinStack() {
    }
    
    public void Push(int x) {
       if (minStack.isEmpty() || x <= minStack.peek())
            {
                minStack.push(x);
            }
            stack.push(x);
    }
    
    public void Pop() {
       if (stack.peek() == minStack.peek())
            {
                minStack.pop();
            }
            stack.pop();
    }
    
    public int Top() {
         return stack.peek();
    }
    
    public int GetMin() {
         return minStack.peek();        
    }
}

2. 顺序栈
   思路与链式栈的相同：

 private int[] s1, s2;
        private int n = 10;// 栈的大小
        private int count = 0;//长度
        private int s2ount = 0;//长度

        /** initialize your data structure here. */
        public MinStack()
        {
            s1 = new int[n];
            s2 = new int[n];
        }

        public void Push(int x)
        {
            if (n == count) return;
            s1[count] = x;

            if (s2ount == 0)
            {
                s2[0] = x;
                ++s2ount;
            }
            else
            {
                int valTop = s1[count - 1];
                if (valTop > x)
                {
                    s2[s2ount] = x;
                    s2ount++;
                }
            }
            ++count;
        }

        public void Pop()
        {
            if (count == 0) return;
            int topval = s1[count - 1];
            --count;
            if (s2ount > 0 && topval <= s2[s2ount - 1])
            {
               -- s2ount;
            }
        }

        public int Top()
        {
            if (count > 0) return s1[count - 1];
            return -999;
        }

        public int GetMin()
        {
            if (s2ount > 0)
                return s2[s2ount - 1];
            return -999;
        }