设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
算法
Java
/**
* 利用辅助栈（minStack）保存栈中最小元素
* 辅助栈的数据与原始的栈数据保持同步
* 时间复杂度O(1)
* 空间复杂度O(n)
*/
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
// 存储最小值的辅助栈
minStack = new Stack<>();
}
public void push(int x) {
if(minStack.isEmpty()){
minStack.push(x);
} else {
// 判断要入栈的数据和最小辅助栈的栈顶数据大小，取小的数据放入最小辅助栈中
if(x <= minStack.peek()){
minStack.push(x);
} else {
minStack.push(minStack.peek());
}
}
stack.push(x);
}
public void pop() {
if(!stack.isEmpty()){
stack.pop();
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
/**
上一步基础上优化最小辅助栈存储的元素
入栈时，如果最新入栈的数据 大于 最小栈的栈顶元素，则此元素不入最小栈
出栈时，如果原始栈的栈顶数据 等于 最小栈的栈顶元素，则全部出栈，否则只有原始栈出栈
*/
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(final int x) {
if(minStack.isEmpty()){
minStack.push(x);
} else {
// 判断要入栈的数据和最小辅助栈的栈顶数据大小，取小的数据放入最小辅助栈中
if(x <= minStack.peek()){
minStack.push(x);
}
}
stack.push(x);
}
public void pop() {
if(!stack.isEmpty()){
int pop = stack.pop();
// 辅助栈的栈顶元素 等于 原始数据栈的栈顶元素
if (minStack.peek() == pop) {
minStack.pop();
}
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
/**
利用链表
*/
class MinStack {
private Node head;
/** initialize your data structure here. */
public MinStack() {
}
public void push(final int x) {
if (head == null){
head = new Node(x, x, null);
} else {
head = new Node(x, Math.min(x, head.min), head);
}
}
public void pop() {
head = head.prior;
}
public int top(){
return head.value;
}
public int getMin(){
return head.min;
}
private class Node{
int value;
int min;
Node prior;
private Node(int value, int min, Node prior) {
this.value = value;
this.min = min;
this.prior = prior;
}
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
swift
// 辅助栈
class MinStack {
var stack: [Int]
var minStack: [Int]
/** initialize your data structure here. */
init() {
stack = [Int]()
minStack = [Int]()
}
func push(_ x: Int) {
stack.append(x)
if minStack.isEmpty {
minStack.append(x)
} else {
minStack.append(min(x, minStack.last!))
}
}
func pop() {
if !stack.isEmpty {
stack.popLast()
minStack.popLast()
}
}
func top() -> Int {
if stack.isEmpty {
return -1
}
return stack.last!
}
func getMin() -> Int {
if minStack.isEmpty {
return -1
}
return minStack.last!
}
}
/**
* Your MinStack object will be instantiated and called as such:
* let obj = MinStack()
* obj.push(x)
* obj.pop()
* let ret_3: Int = obj.top()
* let ret_4: Int = obj.getMin()
*/
// 辅助节点
class MinStack {
var head: Node? = nil
/** initialize your data structure here. */
init() {
}
func push(_ x: Int) {
if head == nil {
head = Node(value: x, minValue: x, prior: nil)
} else {
head = Node(value: x, minValue: min(x, head!.minValue), prior: head!)
}
}
func pop() {
head = head?.prior
}
func top() -> Int {
return head!.value
}
func getMin() -> Int {
return head!.minValue
}
}
class Node {
var value: Int = 0
var minValue: Int = Int.max
var prior: Node? = nil
init(value: Int, minValue: Int, prior: Node?) {
self.value = value
self.minValue = minValue
self.prior = prior
}
}
/**
* Your MinStack object will be instantiated and called as such:
* let obj = MinStack()
* obj.push(x)
* obj.pop()
* let ret_3: Int = obj.top()
* let ret_4: Int = obj.getMin()
*/
网友评论