[数据结构与算法]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）

🤔解题思路

看到取最小，我们第一时间想到用一个变量从第一个位置开始，遇到小的就替换，进行更新，但是这个地方是不可取的，因为这个题目需要的是一个始终保持能找到最小数据的栈。而这个地方假如说这里开始出数据，把最小值给删除了，那么我们就不能很好的找到剩下的最小数据了，需要从头遍历，这就不符合题目的常数时间要求了。我们可以用一个辅助栈来解决这个问题，使得最小的数据被删除后仍然能很好的找到下一个最小的数据。

1. 先存储第一个数。
2. 每次遇到比最小值要小的数据就存储到辅助栈mst上，这里注意等于最小值的数据也要放进去，因为每次删除最小数据后，与它相等的那个数据必然也是最小。
3. 每次弹出数据后，通过辅助栈更新最小值（往前找）

时间复杂度：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++的特性：封装。通过两个栈模拟出最小栈