当前位置: 首页 > news >正文

【LeetCode 热题 100】155. 最小栈

Problem: 155. 最小栈
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

文章目录

  • 整体思路
  • 完整代码
  • 时空复杂度
    • 时间复杂度:O(1)
    • 空间复杂度:O(N)

整体思路

这段代码旨在实现一个经典的特殊数据结构:最小栈 (Min Stack)。这个数据结构除了支持常规栈的 pushpoptop 操作外,还必须支持一个 getMin 操作,该操作能够以 常数时间 O(1) 返回栈中当前的最小元素。

该算法的核心思想是,不只在栈中存储元素值本身,而是 将每个元素与其“当时”的栈内最小值绑定在一起存储

  1. 数据结构选择

    • 算法选择了一个双端队列 Deque<int[]> 并将其用作栈。
    • 关键在于,栈中存储的不是单个整数,而是一个大小为 2 的整型数组 int[]。这个数组被设计成一个元组(pair){value, current_minimum}
      • pair[0] 存储的是被 push 进栈的实际值 val
      • pair[1] 存储的是当这个 val 被压入时,栈内所有元素(包括 val)的最小值
  2. 核心操作逻辑

    • push(val): 当一个新值 val 被推入栈时,算法会创建一个新的元组。新元组的第二部分(current_minimum)通过比较 val上一个状态的最小值(即当前栈顶元组的第二部分 getMin())来确定。这样,每个层级的栈都“知道”自己及以下所有元素的最小值。
    • getMin(): 由于每个状态都保存了到它为止的最小值,获取整个栈的最小值就变得非常简单:只需查看当前栈顶元组的第二部分 st.peek()[1] 即可。这是一个 O(1) 操作。
    • top(): 获取栈顶元素的值,同样只需查看当前栈顶元组的第一部分 st.peek()[0]
    • pop(): 弹出栈顶元组。这个操作非常巧妙,因为当一个元组被弹出后,新暴露出的栈顶元组中保存的最小值,就自动地变回了上一个状态的最小值,无需任何额外计算。
  3. 初始化处理

    • 构造函数中 st.push(new int[]{0, Integer.MAX_VALUE}); 的操作是一个哨兵节点(Sentinel Node)。它的目的是简化 push 操作的逻辑。通过预置一个最小值为 Integer.MAX_VALUE 的节点,第一次调用 push 时,Math.min(getMin(), val) 就能自然地得到 val 作为第一个真正的最小值,从而避免了在 push 方法中写 if (st.isEmpty()) 的特殊判断。

完整代码

/*** 一个支持在常数时间内检索到最小元素的栈。*/
class MinStack {// 使用 Deque 作为栈的底层实现。// 存储的是一个大小为2的数组,格式为 {value, current_minimum}。private final Deque<int[]> st = new ArrayDeque<>();/*** 构造函数,初始化最小栈。*/public MinStack() {// 推入一个哨兵节点或初始节点。// Integer.MAX_VALUE 确保第一个被推入的真实元素的最小值就是它自身。// 这样可以避免在 push 方法中对空栈进行特殊处理。st.push(new int[]{0, Integer.MAX_VALUE});}/*** 将元素 val 推入栈中。* @param val 要推入的元素值*/public void push(int val) {// 创建一个新的元组 {val, min(当前最小值, val)}。// getMin() 会返回上一个状态的最小值。// 将新值与上一个状态的最小值比较,得到新的当前最小值。st.push(new int[]{val, Math.min(getMin(), val)});}/*** 删除栈顶的元素。*/public void pop() {// 直接弹出栈顶的元组 {value, current_minimum}。// 栈的状态(包括最小值)会自动恢复到上一个状态。st.pop();}/*** 获取栈顶元素。* @return 栈顶元素的值*/public int top() {// 栈顶元组的第一个元素 [0] 存储的是实际值。return st.peek()[0];}/*** 在常数时间内检索到栈中的最小元素。* @return 栈中的最小元素值*/public int getMin() {// 栈顶元组的第二个元素 [1] 存储的是到当前状态为止的最小值。return st.peek()[1];}
}

时空复杂度

时间复杂度:O(1)

  1. push(val): 该操作包括 getMin() (即 peek)、Math.minst.push()。对于 ArrayDeque,这些都是 O(1) 的均摊时间复杂度。
  2. pop(): st.pop()O(1) 的均摊时间复杂度。
  3. top(): st.peek()O(1) 的时间复杂度。
  4. getMin(): st.peek()O(1) 的时间复杂度。

综合分析
该数据结构的所有公开操作(push, pop, top, getMin)都具有 O(1) 的时间复杂度,满足了设计要求。

空间复杂度:O(N)

  1. 主要存储开销:空间复杂度由栈 st 的大小决定。
  2. 空间大小:对于用户推入的每一个元素,我们都在栈中存储一个包含两个整数的数组 int[]。如果栈中有 N 个元素(不包括哨兵节点),那么实际存储了 Nint[2] 对象。
  3. 综合分析
    所需的额外空间与栈中元素的数量 N 成线性关系。因此,空间复杂度为 O(N)

参考灵神

http://www.lryc.cn/news/607414.html

相关文章:

  • 【东枫科技】DreamHAT+
  • 【人工智能-17】机器学习:KNN算法、模型选择和调优、朴素贝叶斯分类
  • kafka快速部署、集成、调优
  • 力扣 hot100 Day62
  • 机器学习sklearn:编码、哑变量、二值化和分段
  • TCP协议的特点和首部格式
  • 同品牌的系列广告要如何保证宣传的连贯性?
  • 广东省省考备考(第六十三天8.1)——判断推理(强化训练)
  • 国产开源大模型崛起:使用Kimi K2/Qwen2/GLM-4.5搭建编程助手
  • Galaxea机器人由星海图人工智能科技有限公司研发的高性能仿人形机器人
  • 大模型结构比较
  • uniapp 开发微信小程序,获取经纬度(uni.getLocation)并且转化详细地址(‌高德地图逆地理编码API、‌腾讯地图逆地理编码)
  • SIP 呼叫中实现远端摄像头控制学习笔记
  • axios请求的取消
  • 什么是链游
  • Spring Boot Actuator 保姆级教程
  • JavaWeb--Student2025项目:增删改查
  • 七彩喜艾灸机器人:让传统艾灸变简单,健康养生触手可及
  • HarmonyOS 应用拉起系列(一):应用与元服务互通方式
  • 乐观锁是数据库和多线程编程中常用的一种控制并发的方法
  • 【数据可视化-77】中国历年GDP数据可视化分析:Python + Pyecharts 深度洞察(含完整数据、代码)
  • 伞状Meta分析重构癌症幸存者照护指南:从矛盾证据到精准决策
  • OSPF综合实验报告册
  • 从游戏NPC到手术助手:Agent AI重构多模态交互,具身智能打开AGI新大门
  • 基于倍增的LCA + kruskal重构树 + 并查集
  • 第三章 网络安全基础(一)
  • 【Redis】key的设计格式
  • dolphinscheduler中一个脚本用于从列定义中提取列名列表
  • 香港正式启动稳定币牌照制度!推动中国的人民币国际化?
  • SQL中的LEFT JOIN