原文链接 [每日 LeetCode] 155. Min Stack
Description:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
本题要求设计一个最小栈,即在原有栈的方法中加入
getMin()
方法。
思路一:最开始想到的是使用 vector 来实现,最后运行起来效率太低,不推荐。
思路二:使用两个栈,一个正常操作,另一个栈保证栈顶元素最小,这个效率很高,也是 LeetCode 高赞答案,值得推荐。
C++ 代码(思路一,不推荐)
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
vec.push_back(x);
}
void pop() {
vec.pop_back();
}
int top() {
return vec[vec.size() - 1];
}
int getMin() {
return *min_element(vec.begin(), vec.end());
}
private:
vector<int> vec;
};
/**
* 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();
*/
运行时间:208ms
运行内存:17.1M
C++ 代码(思路二,推荐)
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
s1.push(x);
if (s2.empty() || x <= getMin()) s2.push(x);
}
void pop() {
if (s1.top() == getMin()) s2.pop();
s1.pop();
}
int top() {
return s1.top();
}
int getMin() {
return s2.top();
}
private:
stack<int> s1, s2;
};
/**
* 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();
*/
运行时间:32ms
运行内存:17M
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于