leetcode 剑指 offer 面试题30. 包含min函数的栈
文章目录
本题与 leetcode 155 题相同:https://leetcode-cn.com/problems/min-stack/
不使用额外空间无法做到 O(1) 复杂度。
定义一个额外的栈 m 储存当前的最小值。
参考和详细解析:liweiwei1419 的题解
python 解法
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.s = []
self.m = []
def push(self, x: int) -> None:
if not self.m or x <= self.m[-1]:
self.m.append(x)
self.s.append(x)
def pop(self) -> None:
x = self.s.pop()
if x == self.m[-1]:
self.m.pop()
return x
def top(self) -> int:
return self.s[-1]
def min(self) -> int:
return self.m[-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.min()
c++ 解法
#include <stack>
class MinStack {
stack<int> s, m;
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
s.push(x);
if (m.empty() || x <= m.top()) {
m.push(x);
}
}
void pop() {
if (m.top() == s.top()) {
m.pop();
}
s.pop();
}
int top() {
return s.top();
}
int min() {
return m.top();
}
};
/**
* 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->min();
*/

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