百合网网站建设与策划,龙岗网站建设公司电话,wordpress 建站容易吗,公司软件定制开发leetcode 155. 最小栈 题目 设计一个支持 push #xff0c;pop #xff0c;top 操作#xff0c;并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获…leetcode 155. 最小栈 题目 设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。 题目链接 . - 力扣LeetCode 文字 和 画图 分析 这道题最关键的一点就是在O1的时间复杂度得到最小的元素 如果只有一个栈得到最小的元素就是遍历一遍链表但是时间复杂度是 ON所以这种思路是行不通的 这里我们有另一种思路有两个栈一个正常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();}stackint s1;stackint s2;
};
