题目地址:剑指 Offer 30. 包含min函数的栈 - 力扣(LeetCode)
目录
一.算法思想
二.代码实现
三.拓展思考
首先说结论,这道题虽然难度不大,但是算法思想很重要,是辅助栈应用的生动实例。
所以,这里小编不再重点将代码,而是讲思想。
一.算法思想
本题使用了辅助栈的思想,小编私以为叫同步栈更加合适。
首先一个栈用来正常存放,记作st。
再设一个栈用来存放最小值,记作st_min。
这里的难点就是在st出栈后,假如出栈元素就是最小值,那么怎么回溯到上一个最小值。
本题的最核心的思想就是:
当st入栈出栈时,st_min同时入栈出栈。即同步栈。
但是st_min入栈的值始终是此时的最小值。
即,如果此时st入栈值小于st_min,那st_min入该值。
但如果st入栈值大,那st_min继续入自己的栈顶元素,即最小值。
以图举例:
此时st中入了三个元素,但后两个元素都比st_min的栈顶元素1大,所以st_min依旧入自己栈顶元素。
但当-3入栈st后,-3小于1,所以st_min开始入栈-3。
出栈时就是正常出栈,当st中-2出栈,st_min也同步出栈-3。
这样就可以利用同步栈的特性,完美的解决了当出栈值就是最小值时,回溯到上一个最小值的问题。这也就是本题最核心的算法。
二.代码实现
class MinStack {
stack<int> st;
stack<int> st_min;
public:
MinStack()
{
st_min.push(INT_MAX);//首先装入一个最大值,确保第一个入栈元素能入st_min
}
void push(int x) {
st.push(x);
if(x < st_min.top())
st_min.push(x);
else st_min.push(st_min.top());
}
void pop() {
st.pop();
st_min.pop();
}
int top() {
return st.top();
}
int min() {
return st_min.top();
}
};
三.拓展思考
小编感觉遇到栈和队列的问题,不妨多思考思考多个栈和多个队列组合、混合组合的方式。
这往往能用来解决问题。
比如最经典的用栈实现队列 Loading Question... - 力扣(LeetCode)
用队列实现栈225. 用队列实现栈 - 力扣(LeetCode)
这些都是非常经典的算法思想启发题。
在小编看来,解题最重要的不在难度,而是对于思想的启发。人是在创新中前进而不是在固步自封的强化中前进。
拼命干活无法取代理解。—— H William
如有错误,敬请斧正