leetcode——155. 最小栈
- 🔍题目详情
- 🤔解题思路
- 💻代码实现
- 💬总结
👀先看这里👈
😀作者：江不平
📖博客：江不平的博客
📕学如逆水行舟，不进则退
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
❀本人水平有限，如果发现有错误的地方希望可以告诉我，共同进步👍
🔍题目详情
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop()删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
示例
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出： [null,null,null,null,-3,null,0,-2]
题目来源：力扣（LeetCode）
🤔解题思路
看到取最小，我们第一时间想到用一个变量从第一个位置开始，遇到小的就替换，进行更新，但是这个地方是不可取的，因为这个题目需要的是一个始终保持能找到最小数据的栈。而这个地方假如说这里开始出数据，把最小值给删除了，那么我们就不能很好的找到剩下的最小数据了，需要从头遍历，这就不符合题目的常数时间要求了。我们可以用一个辅助栈来解决这个问题，使得最小的数据被删除后仍然能很好的找到下一个最小的数据。
- 先存储第一个数。
- 每次遇到比最小值要小的数据就存储到辅助栈mst上，这里注意等于最小值的数据也要放进去，因为每次删除最小数据后，与它相等的那个数据必然也是最小。
- 每次弹出数据后，通过辅助栈更新最小值（往前找）
时间复杂度：O(1)
空间复杂度：O(N)
💻代码实现
c++
class MinStack {
public:MinStack() {}void push(int val) {st.push(val);if(minst.empty()||val<=minst.top()){minst.push(val);}}void pop() {if(st.top()==minst.top()){minst.pop();}st.pop();}int top() {return st.top();}int getMin() {return minst.top();}
private:stack<int> st;stack<int> minst;
};
💬总结
我们充分利用了c++的特性：封装。通过两个栈模拟出最小栈
