【leetcode C++】最小栈

leetcode  155. 最小栈

题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

题目链接 

. - 力扣（LeetCode）

文字 和 画图 分析

这道题最关键的一点就是在O（1）的时间复杂度得到最小的元素

如果只有一个栈，得到最小的元素，就是遍历一遍链表，但是时间复杂度是 O（N），所以这种思路是行不通的

这里我们有另一种思路，有两个栈，一个正常push并且pop数据，另一个push最小的数据（每次push都要和栈顶元素进行对比），并且遇到释放数据时，和栈顶元素对比，决定要不要释放

注意：

实际上，存储最小元素的那个栈，存储的数据实际上是<=栈顶元素（防止被pop掉）

代码

class MinStack 
{
public:
    MinStack()   
    {}
    
    void push(int val) 
    {
        s1.push(val);
        if(s2.empty() || s2.top() >= val)
        {
            s2.push(val);
        }
       
    }
    
    void pop() 
    {
       if(!s2.empty() && top() == s2.top())
       {
           s2.pop();
       }
       s1.pop();
    }
    
    int top() 
    {
       return s1.top();
    }
    
    int getMin() 
    {
       return s2.top();
    }
    stack<int> s1;
    stack<int> s2;
};