☆打卡算法☆LeetCode 155. 最小栈 算法解析
☆打卡算法☆LeetCode 155. 最小栈 算法解析
恬静的小魔龙
发布于 2022-08-07 10:40:59
发布于 2022-08-07 10:40:59
一、题目
1、算法题目
“实现MinStack类，实现push/pop/top操作。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
示例 1：
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.示例 2：二、解题
1、思路分析
这道题是实现MinStack类，实现push/pop/top操作。
要解决这道题，首先需要了解的是栈的性质。
栈结构是先进后出的结构，当一个元素入栈时，栈内的其他元素一定还在栈内。
直到栈内的其他元素弹出后，新元素才能出栈。
那么就可以在每个元素入栈的时候，保存栈内最小值，那么无论何时，栈顶元素都是存储的最小值。
2、代码实现
代码参考：
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
image.png
3、时间复杂度
时间复杂度：O(1)
因为栈的插入、删除和读取的操作都是O(1)。
空间复杂度：O(n)
其中n是总操作数，在最坏情况下，会连续插入n个元素。
三、总结
用一个栈，这个栈同时保存的是每个数字进栈的时候的值 与 插入该值后的栈内最小值。
即每次新元素入栈的时候保存一个元组： （当前值 ，栈内最小值） 。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-06-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录