##题目
####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.
##解题思路
这道题实现一个最小栈的问题,这里通过压入每个元素的同时,在压入此时整个栈中的最小值。这样栈里的元素其实是压入元素与当前最小值间的交叉排列。
##算法代码
代码采用JAVA实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
|
class { LinkedList<Integer> stack=new LinkedList<Integer>(); public void push(int x) { if(stack.isEmpty()) { stack.push(x); stack.push(x); }else{ int min=stack.peek(); stack.push(x); if(x>min) { stack.push(min); }else{ stack.push(x); } } }
public void pop() { if(stack.isEmpty()) return; else { stack.pop(); stack.pop(); } }
public int top() { if(stack.isEmpty()) return -1; else{ int num=stack.pop(); int res=stack.peek(); stack.push(num); return res; } }
public int getMin() { if(stack.isEmpty()) return -1; else return stack.peek(); } }
|
近期评论