题目
法1:两个栈实现最小栈
Python
class MinStack:
def __init__(self):
self.stack1 = list()
self.stack2 = list()
def push(self, val: int) -> None:
self.stack1.append(val)
if len(self.stack2) == 0 or self.stack2[-1] >= val:
self.stack2.append(val)
def pop(self) -> None:
top_val = self.stack1.pop()
if top_val == self.stack2[-1]:
self.stack2.pop()
def top(self) -> int:
return self.stack1[-1]
def getMin(self) -> int:
return self.stack2[-1]
Java
class MinStack {
Stack<Integer> stack1;
Stack<Integer> stack2;
public MinStack() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int val) {
stack1.push(val);
if (stack2.isEmpty()) {
stack2.push(val);
} else if (val <= stack2.peek()) {
stack2.push(val);
}
}
public void pop() {
int val = stack1.pop();
if (val == stack2.peek()) {
stack2.pop();
}
}
public int top() {
return stack1.peek();
}
public int getMin() {
return stack2.peek();
}
}