题目描述
设计一个支持 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.
一、CPP
1. 双栈法：
解题思路:投机取巧，使用两个栈，一个栈满足所有的要求。另一个辅助栈用来保存栈的最小值。在计算最小值时，tmp栈顶存放当前最小值，入栈时只判断小于栈顶即可入栈，其他元素(4、5)不用入栈，就算1被pop出后，有2在，他们也算不上是最小值。
时间复杂度:O(1)，“出栈”、“入栈”、“查看栈顶元素”的操作不论数据规模多大，都只是有限个步骤。
空间复杂度:O(n)，n为数据的个数。
class MinStack {
public:
/** initialize your data structure here. */
stack<int> mystack;
//tmp用来保存最小值
stack<int> tmp;
MinStack() {
}
void push(int x) {
mystack.push(x);
if(tmp.empty() || tmp.top() >= x){
tmp.push(x);
}
}
void pop() {
if(mystack.top() == tmp.top()){
tmp.pop();
}
mystack.pop();
}
int top() {
return mystack.top();
}
int getMin() {
return tmp.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->getMin();
*/
- 注意：tmp的入栈条件必须是
tmp.top() >= x，而不能是tmp.top() >x。因为tmp.top() >x在测试用例为下时不满足。
["MinStack","push","push","push","getMin","pop","getMin"]
[[],[2],[1],[1],[],[],[]]
2. 数组双元法：
解题思路:使用vector来模拟栈，vector中存放的元素为pair类型，pair.first为元素值，pair.second为目前为止，“栈”中的最小元素。维护一个min_val变量来设置每次入栈时的最小值。min_val需要注意的三点就是：
- 1.当x <= min_val时需要更新最小值
- 2.当“栈”为空时需要更新最小值
- 3.当把栈顶元素pop出后，需要更新min_val为次栈顶的pair.second。即把min_val更新为当前最新的最小值。
时间复杂度:O(1)。有限操作次数。
空间复杂度:O(n)。
class MinStack {
public:
/** initialize your data structure here. */
vector< pair<int,int> > vec;
int min_val = INT_MAX;
MinStack() {
}
void push(int x) {
if(x <= min_val || vec.size() == 0){
min_val = x;
}
vec.push_back(make_pair(x,min_val));
}
void pop() {
vec.pop_back();
int length = vec.size();
if(length>0){
min_val = vec[length-1].second;
}
}
int top() {
int length = vec.size();
return vec[length-1].first;
}
int getMin() {
int length = vec.size();
return vec[length-1].second;
}
};
/**
* 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();
*/
3. 一栈双元法：（思想同2）
class MinStack {
public:
/** initialize your data structure here. */
stack< pair<int,int> > mystack;
int min_val = INT_MAX;
MinStack() {
}
void push(int x) {
if(x <= min_val || mystack.empty()){
min_val = x;
}
mystack.push(make_pair(x,min_val));
}
void pop() {
mystack.pop();
if(!mystack.empty()){
min_val = mystack.top().second;
}
}
int top() {
pair<int,int> tmp = mystack.top();
return mystack.top().first;
}
int getMin() {
return mystack.top().second;
}
};
/**
* 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();
*/
二、Java（双栈法）
public class MinStack {
private Stack<Integer> s1 = new Stack<>();
private Stack<Integer> s2 = new Stack<>();
public MinStack() {}
public void push(int x) {
s1.push(x);
if (s2.isEmpty() || s2.peek() >= x) s2.push(x);
}
public void pop() {
int x = s1.pop();
if (s2.peek() == x) s2.pop();
}
public int top() {
return s1.peek();
}
public int getMin() {
return s2.peek();
}
}
/**
* 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
1、双栈法
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.mystack = []
self.tmp = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.mystack.append(x)
if len(self.tmp) == 0 or self.tmp[-1] >= x:
self.tmp.append(x)
def pop(self):
"""
:rtype: None
"""
# pop会返回删除的值
x = self.mystack.pop()
if self.tmp[-1] == x:
self.tmp.pop()
def top(self):
"""
:rtype: int
"""
return self.mystack[-1]
def getMin(self):
"""
:rtype: int
"""
return self.tmp[-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()
2、一栈双元法：
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min_val = float("inf")
def push(self, x: int) -> None:
if self.min_val >= x or len(self.stack) == 0:
self.min_val = x
self.stack.append((x,self.min_val))
def pop(self) -> None:
self.tmp = self.stack.pop()
if len(self.stack):
self.min_val = self.stack[len(self.stack)-1][1]
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][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()
四、各语言及算法时间复杂度
网友评论