数组

大家好，我是老马。

今天我们一起来学习一下数组这种数据结构。

主要知识

数组需要拆分下面几个部分：

  1. 理论介绍

  2. 源码分析

  3. 数据结构实现？

  4. 题目练习（按照算法思想分类）

  5. 梳理对应的 sdk 包

  6. 应用实战

因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。

为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。

简单介绍1，重点为4。其他不是本系列的重点。

数据结构篇

通用基础

链表

树

哈希表

stack 栈

queue 队列

ordered set 有序集合

heap 堆

graph 图

进阶

并查集

字典树

线段树

树状数组

后缀数组

chat

https://leetcode.cn/studyplan/top-100-liked/

详细介绍一下力扣数据结构之 Monotonic Stack

下面我会带你系统了解一下 LeetCode 中非常重要的数据结构技巧：单调栈（Monotonic Stack），从概念到实战，一步步讲清楚。

🧠 一句话理解什么是单调栈？

单调栈是一种栈结构，始终保持其中的元素“单调递增”或“单调递减”顺序，用于快速找到左/右侧第一个大于或小于当前元素的值或下标。

🧱 单调栈的结构和分类

  • 按照 栈中元素的大小顺序，单调栈分为两种：
类型 栈内顺序 用途
单调递增栈 从栈底到栈顶：值越来越大 用于找“右边第一个更小的数”
单调递减栈 从栈底到栈顶：值越来越小 用于找“右边第一个更大的数”

📌 注意：“单调递增栈” 是用于找 更小值，因为遇到更小的值时才会出栈。

👀 常见应用场景

典型题型 LeetCode 题号 说明
下一个更大元素 496、739、503 找右边第一个比它大的元素
栈中最大矩形 84 柱状图中最大矩形面积
最小栈问题 155 常见栈技巧
单调队列 / 单调栈综合 42、862 接雨水、滑动窗口

🔁 单调栈的通用模板（以单调递增栈为例）

// 用来存索引（为了能计算距离）
Deque<Integer> stack = new ArrayDeque<>();

for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
        int topIndex = stack.pop();
        // 可以在这里处理逻辑，比如更新左边/右边更小值
    }
    stack.push(i);
}

📘 示例题讲解：LeetCode 739. 每日温度

给定一个数组 temperatures，返回一个数组 answer，其中 answer[i] 表示第 i 天之后才会有更高温度的天数。如果没有更高温，填 0。

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prevIndex = stack.pop();
            res[prevIndex] = i - prevIndex; // 当前温度比栈顶高，计算间隔
        }
        stack.push(i); // 栈存的是下标
    }

    return res;
}

✅ 理解点：

  • 栈里始终是「温度递减」的下标。
  • 一旦遇到更高温度，就开始“清算”。

🔍 单调栈 vs 普通栈

项目 普通栈 单调栈
目的 后进先出 维护单调序
应用 通用场景 查找“左右第一个更大/小的值”
出栈条件 无条件 pop 满足单调性被破坏才 pop

🧠 单调栈常见变种

  • 维护值：直接将 nums[i] 入栈（适合不需要索引）
  • 维护索引：将 i 入栈（适合需要计算间隔距离）
  • 哨兵技巧：数组首尾加 0 或 ∞，避免边界处理
  • 双向遍历：处理左边和右边第一个更大/更小值

🧪 小练习题推荐

题目 说明
LeetCode 496. Next Greater Element I 单调栈基础
LeetCode 503. Next Greater Element II 循环数组
LeetCode 84. Largest Rectangle in Histogram 单调栈经典题
LeetCode 42. Trapping Rain Water 单调栈 + 双指针技巧结合

🔚 总结

单调栈的核心价值在于：

  • 快速找出某个元素左右第一个大于/小于它的元素
  • 用于处理那些「相对大小有要求」的区间问题
  • 一般时间复杂度是 O(n)，因为每个元素最多只进栈和出栈一次

我日常使用 java 是不是可以用优先级队列替代

你问得非常好！我们来认真比较一下：日常使用 Java 时，能不能用优先级队列（PriorityQueue）来替代单调栈？

先给出结论：

🧾 简明结论：

不能互相替代。优先级队列和单调栈是两种核心目标不同的数据结构。

✅ 为什么不能替代？

📌 1. 功能不同

数据结构 核心用途 支持操作 特点
单调栈 维护元素单调递增/递减 查找左/右第一个更大/更小元素 位置敏感，顺序相关
优先队列 维护元素整体最大/最小值 快速取最大/最小值 与顺序无关，只在意大小

📌 2. 举例说明（用错就错）

👉 示例一：LeetCode 739 每日温度（找右边第一个更高温度）

你用单调栈：

Deque<Integer> stack = new ArrayDeque<>();
  • 维护的是下标的相对顺序
  • 一旦当前温度比栈顶高 → 出栈并计算「距离」

你如果用 PriorityQueue：

PriorityQueue<Integer> pq = new PriorityQueue<>();
  • 只能拿到最小/最大温度
  • 根本无法知道「这个温度在原数组的哪个位置」

📌 优先队列不保顺序、不支持左右关系 → 完全不适合做“左右第一个比我大/小”的问题！

🔍 容易误用的场景对比

目标 推荐结构 替代可能？
找左右第一个更大/小 单调栈 ✅ ❌
维护当前窗口最大/最小值 单调队列 ✅ 优先队列 ❌（有延迟）
快速取最大/最小元素 优先队列 ✅ ❌
找数组中第 K 大 优先队列 ✅ 单调栈 ❌
维护滑动窗口最大值 单调队列 ✅ 优先队列 ❌（需要懒删除）

🧠 什么时候用单调栈，什么时候用 PriorityQueue？

场景 用这个
需要找“左边/右边第一个比我大/小” → 顺序敏感 单调栈
需要快速找到“当前所有值中的最大/最小值” PriorityQueue
要找 top-K PriorityQueue
要处理区间最大值 / 单调性优化 单调队列 / 单调栈

🧪 实战建议

你写代码时可以这样判断：

❓“我想快速找到一个最大/最小值” → ✅ 用 PriorityQueue

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 最小堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 最大堆

❓“我想找一个值的左边/右边第一个比它大/小的数” → ✅ 用单调栈

Deque<Integer> stack = new ArrayDeque<>();

🧭 总结一句话：

优先级队列用于“全局最大最小”，单调栈用于“相邻关系判断”。

二者无法互相替代，用错结构会导致逻辑错误、性能低下甚至题目做不出来。