剑指offer/LintCode12_最小栈
文章目录
剑指offer/LintCode12_最小栈
声明
文章均为本人技术笔记,转载请注明出处https://segmentfault.com/u/yzwall
解题思路
实现功能:
实现一个最小栈,要求push(element),pop(),min()操作均为$O(1)$复杂度,
解题思路
用栈
stack存储数据;-
用最小栈
minStack存储stack中最小元素,保证minStack栈顶元素与stack栈顶元素同步,minStack.peek()表示此时stack最小值push(number):minStack将number与此时最小值minStack.peek()比较,将更小的一方压栈,保证minStack中栈顶始终为最小值;pop():对stack进行pop()时,同时进行minStack.pop(),保证minStack与stack同步;
注意点
实现最大栈时,
push(number)操作只需push(Math.max(number, minStack.peek()),保证maxStack栈顶元素始终为最大值pop操作时,maxStack与stack同时pop,保证同步;
题目链接
lintcode 12: http://www.lintcode.com/en/problem/min-stack/
Java代码
/**
* 实现一个最小栈,要求push,pop,min操作均为O(1)复杂度
* http://www.lintcode.com/en/problem/min-stack/
* @author yzwall
*/
import java.util.ArrayDeque;
class MinStack {
private ArrayDeque<Integer> stack;
private ArrayDeque<Integer> minStack;
MinStack() {
this.stack = new ArrayDeque<>();
this.minStack = new ArrayDeque<>();
}
public void push(int number) {
stack.push(number);
if (minStack.isEmpty()) {
minStack.push(number);
} else {
// 实现最大栈时,只需push(Math.max(number, minStack.peek())
minStack.push(Math.min(number, minStack.peek()));
}
}
public int pop() {
minStack.pop();
return stack.pop();
}
public int min() {
return minStack.peek();
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论