tag: 栈（stack）
题目描述
设计一个支持 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.
python版本：
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min = None
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.stack.append(x)
if self.min == None or x < self.min:
self.min = x
def pop(self):
"""
:rtype: None
"""
popItem = self.stack.pop()
if len(self.stack) == 0:
self.min = None
return popItem
if popItem == self.min:
self.min = self.stack[0]
for i in self.stack:
if i < self.min:
self.min = i
return popItem
def top(self):
"""
:rtype: int
"""
return self.stack[-1]
def getMin(self):
"""
:rtype: int
"""
return self.min
if __name__ == "__main__":
obj = MinStack()
obj.push(12)
obj.push(14)
obj.push(54)
print(obj.pop())
print(obj.top())
print(obj.getMin())
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
java版本：
import java.util.Stack;
class MinStack {
/** initialize your data structure here. */
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> min = new Stack<Integer>();
public void push(int x) {
if (this.stack.isEmpty()){
this.stack.push(x);
this.min.push(x);
} else {
this.stack.push(x);
this.min.push(Math.min(this.stack.peek(), this.min.peek()));
}
}
public void pop() {
if (!this.stack.isEmpty()){
this.stack.pop();
this.min.pop();
}
}
public int top() {
if (!this.stack.isEmpty()){
return this.stack.peek();
}
throw new IllegalStateException();
}
public int getMin() {
if (!this.min.isEmpty()){
return this.min.peek();
}
throw new IllegalStateException();
}
}
/**
* 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();
*/