- 难度：
简单 - 本题涉及算法：
前缀和暴力哈希表 - 思路：
前缀和暴力哈希表 - 类似题型:
题目 155. 最小栈
设计一个支持 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 操作总是在 非空栈 上调用。
方法一 数组
解题思路
- 我们先用最快捷的方式做题，在慢慢优化代码
- 使用数组，做数据的增删差操作
- 而对于获取最小值 使用
Collections.min(list)获取
java
class MinStack {
// 数据
List<Integer> list = null;
/** initialize your data structure here. */
public MinStack() {
list = new ArrayList<>();
}
public void push(int x) {
list.add(x);
}
public void pop() {
list.remove(list.size()-1);
}
public int top() {
return list.get(list.size()-1);
}
public int getMin() {
return Collections.min(list);
}
}
/**
* 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();
*/
方法二 辅助栈
解题思路
- 显然 直接使用
Collections.min(list)拿到最最小数 会触发隐藏剧情(Collections.min 是怎么实现的) - 是的，这里可以用栈，而且用两个，一个是数据栈，一个是辅助栈
- 数据栈好理解 而辅助栈则是用在 获取最小值中， 通过把最小值放在辅助栈栈顶，来获取最小数据
- 上代码
java
class MinStack {
// 数据栈
private Stack<Integer> data;
// 辅助栈 用于获取最小值
private Stack<Integer> helper;
/** initialize your data structure here. */
public MinStack() {
data = new Stack<>();
helper = new Stack<>();
}
public void push(int x) {
data.add(x);
if (helper.isEmpty() || helper.peek()>=x)
helper.add(x);
else
helper.add(helper.peek());
}
public void pop() {
if(!data.isEmpty()) {
data.pop();
helper.pop();
}
}
public int top() {
if(!data.isEmpty())
return data.peek();
throw new RuntimeException("栈中元素为空，此操作非法");
}
public int getMin() {
if(!data.isEmpty()) {
return helper.peek();
}
throw new RuntimeException("栈中元素为空，此操作非法");
}
}
/**
* 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();
*/
python
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = [] # 数据栈
self.helper = [] # 辅助栈
def push(self, x: int) -> None:
self.stack.append(x)
if not self.helper or self.helper[-1] >= x:
self.helper.append(x)
else:
self.helper.append(self.helper[-1])
def pop(self) -> None:
if self.stack:
self.helper.pop()
return self.stack.pop()
def top(self) -> int:
if self.stack:
return self.stack[-1]
def getMin(self) -> int:
if self.helper:
return self.helper[-1]
# 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()
PREVIOUS面试题 08.11. 硬币