leetcode 155. Min Stack 最小栈 (中等)

2022 年 8 月 08 日
本文字数：1032 字
阅读完需：约 3 分钟

一、题目大意

标签: 栈和队列

设计一个支持 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.

提示：

-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在非空栈上调用
push, pop, top, and getMin 最多被调用 3 * 104 次

二、解题思路

可以额外建立一个栈（最小值栈），栈顶表示原栈中最小值。插入一个数字时，如果该值小于新栈的栈顶值说明该数是最小值，将其同时插入原栈和最小值栈。取数时，如果原栈的值等于最小值栈的值，说明这个数是原栈中的最小值，原栈和最小值栈需要同时移除该元素。

实现：每次插入栈时，都向最小值栈插入一个原栈里所有值的最小值。

三、解题方法

3.1 Java 实现

class MinStack {    Stack<Integer> s;    /**     * 辅助栈     */    Stack<Integer> minS;
    public MinStack() {        s = new Stack<>();        minS = new Stack<>();    }
    public void push(int val) {        s.push(val);        // 注意这里是>=        if (minS.isEmpty() || minS.peek() >= val) {            minS.push(val);        }    }
    public void pop() {        int val = s.pop();        if (!minS.isEmpty() && minS.peek() == val) {            minS.pop();        }    }
    public int top() {        return s.peek();    }
    public int getMin() {        return minS.isEmpty() ? 0 : minS.peek();    }}
// Integer 与 int 比较
/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

复制代码

四、总结小记

2022/8/8 这两天有大到暴雨，能凉快一些吧

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/47a48bd3916fb01fe41e075d9】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

一年当十年用的Java程序员

发布

暂无评论

创作场景