【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;};

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/xuetang/2024-03-25/148583.html，文章来源：网络cs，作者：利杜鹃，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！