LeetCode-155. 最小栈(java)

bug菌

发布于 2023-05-27 15:10:12

1270

发布于 2023-05-27 15:10:12

文章被收录于专栏：《项目实战教学》《项目实战教学》

一、前言：

👨‍🎓作者：bug菌 ✏️博客：CSDN、掘金等 💌公众号：猿圈奇妙屋 🚫特别声明：原创不易，转载请附上原文出处链接和本文声明，谢谢配合。 🙏版权声明：文章里可能部分文字或者图片来源于互联网或者百度百科，如有侵权请联系bug菌处理。

题目：

设计一个支持 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^31 <= val <= 2^31 - 1
pop、top 和 getMin 操作总是在非空栈上调用
push, pop, top, and getMin最多被调用 3 * 10^4 次

题目来源：LeetCode官网题目难度：⭐⭐

三、思路分析：

分析题意，如果对栈的先进后出特点有所了解，这题应该也不难。

这题最好的方式就是借用一个辅助栈minStack，用于存获取stack中的最小值。

算法流程：

push()方法：

每当push()新值进来时，如果 <= minStack 栈顶值，则一起push()到minStack，即更新了栈顶最小值；

pop()方法：

判断将pop()出去的元素值是否是minStack栈顶元素值（即最小值），如果是则将minStack栈顶元素一起pop()，这样可以保证minStack栈顶元素始终是stack中的最小值。

getMin()方法：

返回minStack栈顶即可。

minStack作用分析：

minStack等价于遍历stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。相当于给stack中的降序元素做了标记，每当pop()这些降序元素，minStack会将相应的栈顶元素pop()出去，保证其栈顶元素始终是stack中的最小元素。

动画演示：

四、算法实现：

AC代码

具体算法代码实现如下：

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 {
        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