设计一个支持 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.
思路：
-
链式栈：
使用两个链式栈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();
}
}
-
顺序栈
思路与链式栈的相同：
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;
}
