LeetCode 补充题 126. 支持最大值和最小值查询的栈

约 4 分钟
文章信息 3 个分类 2 个标签
分类
补充题 中等 字节
标签
栈 链表

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ 155. 最小栈

:::

请实现一个整数栈，支持 push、pop、top、getMin 和 getMax 操作。

  • push(value)：将 value 压入栈顶。
  • pop()：删除并返回栈顶元素。
  • top()：返回栈顶元素。
  • getMin()：返回栈内最小值。
  • getMax()：返回栈内最大值。

要求每个操作的最坏时间复杂度均为 O(1)。调用出栈和查询操作前，保证栈非空。

示例 1：

输入： 操作 = [push(3), push(1), push(1), push(5), getMin(), getMax(), pop(), getMax()]
输出： 查询及出栈结果 = [1,5,5,3]
解释： push 不产生查询结果。弹出 5 后，剩余元素的最大值恢复为 3；重复的两个 1 均保留。

提示：

  • 各操作最坏 O(1)。
  • 调用 pop、top、getMin、getMax 前保证栈非空。
  • 允许重复值。

题意分析

只保存当前最小值和最大值不足以处理出栈：极值被弹出后，还需要立即知道剩余栈的极值。栈按后进先出恢复历史状态，适合为每一层保存它对应的极值快照。

解法：每个链式栈节点保存前缀极值

核心思路

[!blue]

每个节点保存当前值，以及该节点和它下面所有节点的 min、max。新节点入栈时，分别将当前值与旧栈顶的极值比较；空栈入栈则两者都等于当前值。

出栈只将 head 移到下一个节点，旧节点中保存的极值正好对应剩余元素，无需重新计算。重复极值也不会丢失，因为每一层都独立保存当时的完整极值。

查询直接读取栈顶字段。使用链式节点没有动态数组扩容搬移，在通常的节点分配模型下，各操作只处理常数个字段；题面保证查询和出栈前非空。

解题步骤

  1. 新节点保存入栈值，以及与旧栈顶 min/max 比较后的新极值。
  2. 把新节点作为栈顶；pop 读取顶值后把头指针移到下一节点。
  3. top、getMin、getMax 直接读取当前栈顶字段。

代码实现

class MinMaxStack {
    private static class Node {
        int value;
        int min;
        int max;
        Node next;

        Node(int value, Node next) {
            this.value = value;
            this.next = next;
            min = next == null ? value : Math.min(value, next.min);
            max = next == null ? value : Math.max(value, next.max);
        }
    }

    private Node head;

    public void push(int value) {
        head = new Node(value, head);
    }

    public int pop() {
        int value = head.value;

        head = head.next;

        return value;
    }

    public int top() {
        return head.value;
    }

    public int getMin() {
        return head.min;
    }

    public int getMax() {
        return head.max;
    }
}

type minMaxNode struct {
    value, min, max int
    next            *minMaxNode
}
type MinMaxStack struct{ head *minMaxNode }

func (s *MinMaxStack) Push(value int) {
    node := &minMaxNode{value: value, min: value, max: value, next: s.head}
    if s.head != nil {
        node.min = min(value, s.head.min)
        node.max = max(value, s.head.max)
    }
    s.head = node
}

func (s *MinMaxStack) Pop() int {
    value := s.head.value
    s.head = s.head.next
    return value
}

func (s *MinMaxStack) Top() int {
    return s.head.value
}

func (s *MinMaxStack) GetMin() int {
    return s.head.min
}

func (s *MinMaxStack) GetMax() int {
    return s.head.max
}

复杂度分析

  • 时间复杂度：每个操作最坏时间 $O(1)$。
  • 空间复杂度：总空间 $O(n)$。

关键点总结

[!green]

每层保存的是到该层为止的完整极值状态，弹出一层就恢复上一份快照，无需重新扫描。

易错点总结

[!yellow]

每层都保存极值，重复最小值或最大值出栈不会丢失此前统计。

相似题目

题目 难度 关联与区别
155. 最小栈 中等 在每层最小值快照的基础上再保存最大值，重复极值的出栈也能自然恢复旧状态。
716. 最大栈 困难 本题只查询最大值；若还要删除内部最大元素，单纯的栈顶极值快照不够。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/66540563
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！