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.
分析：设计一个堆栈支持push，pop，top以及以常数时间检索里面的最小元素
思路：
1、用两个stack来解决：第一个stack用来正常进行stack的push，pop和top操作；另外一个min_stack用来存储最小元素.每次对stack进行pop或者push时，也对min_stack进行相应操作。
2、 第二个min_stack可以进行优化：不一定每个最小元素都要入栈min_stack, push的时候，只入栈比当前min小或者相等的值就可以了。pop的时候，要比较待pop元素和min_stack中top的大小。如果待pop元素和min_stack的top元素相等，则将min stack进行pop。
代码如下：
class MinStack {
private:
std::stack<int> stack;
std::stack<int> min_stack;
public:
void push(int x) {
stack.push(x);
if (min_stack.empty() || ((!min_stack.empty()) && x <= min_stack.top())) { //NOTE: 是“小于等于”，不是“小于”
min_stack.push(x);
}
}
void pop() {
if (!stack.empty()) {
if (stack.top() == min_stack.top())
min_stack.pop();
stack.pop();
}
}
int top() {
if (!stack.empty())
return stack.top();
}
int getMin() {
if (!min_stack.empty())
return min_stack.top();
}
};
或：
class MinStack {
public:
void push(int x) {
if (stk1.empty() || x <= stk2.top())
stk2.push(x);
stk1.push(x);
}
void pop() {
if (stk1.top() == stk2.top())
stk2.pop();
stk1.pop();
}
int top() {
return stk1.top();
}
int getMin() {
return stk2.top();
}
private:
stack<int> stk1;
stack<int> stk2;
};
或者：using two vectors
class MinStack {
public:
vector<int> stack;
vector<int> stmin = {INT_MAX};
void push(int x) {
if(x <= stmin[stmin.size() - 1]) stmin.push_back(x);
stack.push_back(x);
}
void pop() {
if(stack[stack.size() - 1] == stmin[stmin.size() - 1]) stmin.pop_back();
stack.pop_back();
}
int top() {
if(stack.size() == 0) return 0;
return stack[stack.size() - 1];
}
int getMin() {
return stmin[stmin.size() - 1];
}
};
转载于:https://www.cnblogs.com/carsonzhu/p/4684558.html
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/109380.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
