leetcode 155 最小栈

zhaojun

2022 年 09 月 24 日

2360 次浏览

暂无评论

708字数

默认分类

# [155. 最小栈](https://leetcode.cn/problems/min-stack/)

## 题目

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

## 解题思路

可使用双栈实现，一个正常存储数据（stackData），一个每次将最小值压到栈顶（stackMin）。如依次将 3、4、5、1、2、1 压入

![](https://cdn.jun6.net/uPic/2022/09/24/rSs1Fq.png)

## 题解

因题目描述了 `pop`、`top` 和 `getMin` 操作总是在 **非空栈** 上调用，所以这里没有进行非空判断。

```java
import java.util.Stack;

class MinStack {

private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    
    public MinStack() {
        stackData = new Stack<>();
        stackMin = new Stack<>();
    }
    
    public void push(int val) {
        stackData.push(val);

if (stackMin.isEmpty() || val <= stackMin.peek()) {
            stackMin.push(val);
        }
    }
    
    public void pop() {
        Integer data = stackData.pop();
      
        // 此处注意用 equals 而不是 ==
        if (stackMin.peek().equals(data)) {
            stackMin.pop();
        }
    }
    
    public int top() {
        return stackData.peek();
    }
    
    public int getMin() {
        return stackMin.peek();
    }
}

```

最后修改：2022 年 09 月 24 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

leetcode 155 最小栈

zhaojun • 2022 年 09 月 24 日

leetcode 155 最小栈

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

宝塔 nginx 增加编译模块

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

使用 Gost 来实现 sniproxy

修复 docker buildx 编译后，manifest 包含 unknown 的问题

Spring 使用事件监听来解耦代码

2022 年终总结

Shiro 学习 11 - 集成 Spring 之记住我

leetcode 155 最小栈

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 155 最小栈

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款