数组

大家好，我是老马。

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

主要知识

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

  1. 理论介绍

  2. 源码分析

  3. 数据结构实现？

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

  5. 梳理对应的 sdk 包

  6. 应用实战

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

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

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

数据结构篇

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

通用基础

链表

树

哈希表

stack 栈

queue 队列

ordered set 有序集合

heap 堆

graph 图

进阶

并查集

字典树

线段树

树状数组

后缀数组

chat

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

栈（Stack）是 LeetCode 中的高频数据结构之一，常用于括号匹配、表达式求值、单调栈、深度优先搜索等题型。它具有**先进后出（LIFO）**的特点，操作简单、用途广泛。

🧱 一、栈的基本概念

特性 描述
操作方式 先进后出（LIFO）
主要操作 push（压栈）、pop（弹栈）、peek（栈顶）、isEmpty
常见实现 数组、链表、双端队列

🛠️ 二、Java 中的栈结构

类型 特点
Stack<E> 标准栈类（继承自 Vector，线程安全，实际不推荐）
Deque<E> 推荐：用 ArrayDeque 实现栈更高效
LinkedList<E> 也可作为栈使用，但略慢

推荐写法（使用 Deque）：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);        // 入栈
int top = stack.pop(); // 出栈
int peek = stack.peek(); // 查看栈顶

🔁 三、栈的常见应用场景

场景 示例 说明
括号匹配 LC 20 有效括号 左括号入栈，右括号配对出栈
表达式求值 LC 150 逆波兰表达式 数字入栈，操作符出栈两个数计算
单调栈 LC 739 每日温度 维护递增或递减栈找下一个更大/小值
DFS LC 200 岛屿数量 用栈代替递归实现深度优先遍历
历史状态保存 LC 155 最小栈 保存最小值的辅助栈

📘 四、LeetCode 高频题型整理

✅ 括号相关

题号 名称 技巧
20 有效的括号 栈匹配成对符号
32 最长有效括号 栈存下标
301 删除无效括号 栈 + 回溯

🧮 表达式相关

题号 名称 技巧
150 逆波兰表达式求值 遇数字入栈，遇运算符出栈两个数运算
227 基本计算器 II 栈 + 优先级处理
394 字符串解码 嵌套解码，两个栈：数字栈 + 字符串栈

📊 单调栈

题号 名称 技巧
739 每日温度 单调递减栈
496 下一个更大元素 I 模拟压栈寻找下一个更大值
84 柱状图中最大矩形 单调递增栈求左右边界
901 股票价格跨度 单调栈记录连续天数

🧱 其他经典题

题号 名称 技巧
155 最小栈 用辅助栈维护最小值
225 用队列实现栈 两个队列模拟栈行为
232 用栈实现队列 两个栈实现先进先出

🧰 五、常用模板总结

1️⃣ 括号匹配（LC 20）

Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') {
        stack.push(c);
    } else {
        if (stack.isEmpty()) return false;
        char top = stack.pop();
        if (!match(top, c)) return false;
    }
}
return stack.isEmpty();

boolean match(char a, char b) {
    return (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}');
}

2️⃣ 单调栈模板（找下一个更大元素）

Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        int idx = stack.pop();
        res[idx] = nums[i]; // 找到了更大元素
    }
    stack.push(i);
}

3️⃣ 表达式求值（LC 150）

Deque<Integer> stack = new ArrayDeque<>();
for (String token : tokens) {
    if (isOperator(token)) {
        int b = stack.pop(), a = stack.pop();
        stack.push(eval(a, b, token));
    } else {
        stack.push(Integer.parseInt(token));
    }
}

⚠️ 六、栈相关注意事项

注意点 说明
注意索引还是值 单调栈中通常存索引，不是数值本身
嵌套结构处理 可用多个栈分别维护状态（如字符串解码）
辅助栈保存状态 如最小栈，第二个栈保存当前最小值
栈为空判断 任何 pop、peek 操作前请判断是否为空

📚 七、刷题建议路线（由易到难）

    1. 有效的括号 ✅
    1. 最小栈 ✅
    1. 逆波兰表达式 ✅
    1. 每日温度 🟡
    1. 下一个更大元素 🟡
    1. 柱状图最大矩形 🔴
    1. 最长有效括号 🔴
    1. 字符串解码 🔴

✅ 总结一句话

栈的核心是“先进后出”，能帮我们在括号配对、延迟处理、单调关系、表达式求值等问题中快速建模。建议熟练掌握其基本用法和单调栈技巧。

需要我给你整理一份「单调栈题单」或者「表达式求值专题解析」也可以告诉我～