最小栈-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;        }