一、固定模板算法
1. 二分查找
1.1 标准二分查找
javascript
function binarySearch(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}【例题与图解】
题目：LeetCode 704. 二分查找
输入：nums = [-1,0,3,5,9,12], target = 9
输出：4
图解过程：
索引: 0 1 2 3 4 5
值: -1 0 3 5 9 12
初始 left=0, right=5
mid = (0+5)//2 = 2, nums[2]=3 < 9 → left=3
left=3, right=5, mid=4, nums[4]=9 == 9 → 返回4输入：target = 2，输出 -1。
1.2 查找左边界
javascript
function leftBound(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
if (left < nums.length && nums[left] === target) return left;
return -1;
}【例题与图解】
题目：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置（左边界）
输入：nums = [5,7,7,8,8,10], target = 8
输出：3
图解过程：
nums: 5 7 7 8 8 10
索引 0 1 2 3 4 5
初始 L=0,R=5
mid=2, nums[2]=7 <8 → L=3
L=3,R=5, mid=4, nums[4]=8 >=8 → R=3
L=3,R=3, mid=3, nums[3]=8 >=8 → R=2 (L>R)
检查 L=3 未越界且 nums[3]==8 → 返回32. 滑动窗口
2.1 最小覆盖子串
javascript
function minWindow(s, t) {
let need = new Map();
for (let c of t) need.set(c, (need.get(c)||0)+1);
let window = new Map();
let left = 0, right = 0;
let valid = 0;
let start = 0, len = Infinity;
while (right < s.length) {
let c = s[right];
right++;
if (need.has(c)) {
window.set(c, (window.get(c)||0)+1);
if (window.get(c) === need.get(c)) valid++;
}
while (valid === need.size) {
if (right - left < len) {
start = left;
len = right - left;
}
let d = s[left];
left++;
if (need.has(d)) {
if (window.get(d) === need.get(d)) valid--;
window.set(d, window.get(d)-1);
}
}
}
return len === Infinity ? "" : s.substr(start, len);
}【例题与图解】
题目：LeetCode 76. 最小覆盖子串
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
图解过程（文字描述）：
- 窗口右指针逐步扩大，直到包含 A、B、C 各至少一次（如
"ADOBEC"）。 - 记录长度，然后左指针收缩，试图缩小窗口，同时保持覆盖。
- 最终在右指针遍历完后，找到最小窗口
"BANC"（索引 9~12）。
关键步骤示意：
s: A D O B E C O D E B A N C
t: A,B,C
right=5, window="ADOBEC", valid=3 → 记录长度6，收缩左边界
left=1, window="DOBEC", valid=2 → 不满足，继续扩大
...
right=12, left=9, window="BANC", 长度4 → 最终输出2.2 无重复字符的最长子串
javascript
function lengthOfLongestSubstring(s) {
let window = new Map();
let left = 0, right = 0;
let maxLen = 0;
while (right < s.length) {
let c = s[right];
right++;
window.set(c, (window.get(c)||0)+1);
while (window.get(c) > 1) {
let d = s[left];
left++;
window.set(d, window.get(d)-1);
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}【例题与图解】
题目：LeetCode 3. 无重复字符的最长子串
输入：s = "abcabcbb"
输出：3（最长子串为 "abc"）
图解过程：
s: a b c a b c b b
窗口变化：
right=0, window={a:1}, max=1
right=1, window={a:1,b:1}, max=2
right=2, window={a:1,b:1,c:1}, max=3
right=3, c='a', window[a]=2 → 收缩 left=1, window[a]=1, window={a:1,b:1,c:1}, max仍3
...
最终 max=33. 回溯算法
3.1 全排列
javascript
function permute(nums) {
const res = [];
const track = [];
function backtrack(used) {
if (track.length === nums.length) {
res.push([...track]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
track.push(nums[i]);
used[i] = true;
backtrack(used);
track.pop();
used[i] = false;
}
}
backtrack([]);
return res;
}【例题与图解】
题目：LeetCode 46. 全排列
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
用递归树看回溯
以 nums = [1,2,3] 为例，递归树的局部如下：
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] [1,3,2] ...（依次类推）- 从根
[]出发，先走左分支，选择1，到达[1]。 - 在
[1]节点，再走左分支，选择2，到达[1,2]。 - 在
[1,2]节点，只能选3，到达叶子[1,2,3]，记录结果。 - 记录后，回溯：从
[1,2,3]返回[1,2]，并撤销对3的选择（把3放回），此时[1,2]的状态恢复了。 - 然后继续在
[1,2]节点尝试下一个选择（已经没有其他选择了，因为3已经试过且被撤销了），所以返回[1]。 - 在
[1]节点，撤销对2的选择（把2放回），然后尝试下一个选择：选择3，到达[1,3]，再选2，得到[1,3,2]…… - 如此反复，直到所有分支都遍历完。
回溯确保了每个分支都能被独立地探索，而不会相互干扰。
一句话总结
回溯就是“撤销当前选择，恢复现场”，让我们能够在尝试完一条路径后，回到上一个岔路口，去走另一条没走过的路，从而穷举所有可能的排列。
3.2 组合总和
javascript
function combinationSum(candidates, target) {
const res = [];
const track = [];
function backtrack(start, sum) {
if (sum === target) {
res.push([...track]);
return;
}
if (sum > target) return;
for (let i = start; i < candidates.length; i++) {
track.push(candidates[i]);
backtrack(i, sum + candidates[i]);
track.pop();
}
}
backtrack(0, 0);
return res;
}【例题与图解】
题目：LeetCode 39. 组合总和
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
图解过程：
从 start=0 开始：
选2 (sum=2) → 继续选2 (sum=4) → 选2 (sum=6) → 选2 (sum=8>7回溯)
→ 选3 (sum=5) → 选2 (sum=7) 得到 [2,2,3]
→ 选3 (sum=8>7回溯)
→ 选3 (sum=5) ... 最终得到 [7] 单独分支3.3 N 皇后
javascript
function solveNQueens(n) {
const res = [];
const board = Array.from({ length: n }, () => Array(n).fill('.'));
function isValid(row, col) {
for (let i = 0; i < row; i++) if (board[i][col] === 'Q') return false;
for (let i = row-1, j = col-1; i>=0 && j>=0; i--, j--) if (board[i][j] === 'Q') return false;
for (let i = row-1, j = col+1; i>=0 && j<n; i--, j++) if (board[i][j] === 'Q') return false;
return true;
}
function backtrack(row) {
if (row === n) {
res.push(board.map(row => row.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (!isValid(row, col)) continue;
board[row][col] = 'Q';
backtrack(row+1);
board[row][col] = '.';
}
}
backtrack(0);
return res;
}【例题与图解】
题目：LeetCode 51. N 皇后
输入：n = 4
输出：
javascript
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]图解（解法1）：
行0: . Q . .
行1: . . . Q
行2: Q . . .
行3: . . Q .回溯过程逐行放置皇后，检查列和对角线冲突。
4. DFS 与 BFS
4.1 图的 DFS（递归）
javascript
function dfs(graph, start) {
const visited = new Set();
function traverse(node) {
if (visited.has(node)) return;
visited.add(node);
console.log(node); // 访问
const neighbors = graph.get(node) || [];
for (let neighbor of neighbors) traverse(neighbor);
}
traverse(start);
}【例题与图解】
题目：图的深度优先遍历（邻接表）
输入：
javascript
graph = new Map([
[0, [1,2]],
[1, [0,3,4]],
[2, [0,5]],
[3, [1]],
[4, [1]],
[5, [2]]
]);
start = 0;输出：访问顺序示例：0,1,3,4,2,5（取决于具体实现，但 DFS 会深入一条路径再回溯）
图解：从 0 出发，先访问 1，再从 1 访问 3，然后回溯到 1 访问 4，最后回溯到 0 访问 2 和 5。
4.2 二叉树的 BFS（层序遍历）
javascript
function levelOrder(root) {
if (!root) return [];
const res = [];
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.push(level);
}
return res;
}【例题与图解】
题目：LeetCode 102. 二叉树的层序遍历
输入：二叉树 [3,9,20,null,null,15,7]
树结构：
3
/ \
9 20
/ \
15 7输出：[[3],[9,20],[15,7]]
图解：
- 队列初始 [3]，取出 3，记录层 [3]，加入 9,20。
- 队列 [9,20]，取出 9（层 [9]），加入空；取出 20，加入 15,7 → 层 [9,20]。
- 队列 [15,7]，取出 15（层 [15]），取出 7 → 层 [15,7]。
4.3 图的 BFS（最短路径）
javascript
function bfsShortestPath(graph, start, target) {
if (start === target) return 0;
const queue = [start];
const visited = new Set([start]);
let steps = 0;
while (queue.length) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (node === target) return steps;
const neighbors = graph.get(node) || [];
for (let neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
steps++;
}
return -1;
}【例题与图解】
题目：无向无权图最短路径
输入：同 4.1 图，start=0, target=5
输出：2（路径 0→2→5）
图解：
- 第0步：从 0 出发，队列 [0]，visited=
- 第1步：取出 0，加入邻居 1,2 → 队列 [1,2]，steps=1
- 第2步：取出 1（不是5），加入邻居 3,4（已访问略）；取出 2（发现 2 的邻居有 5），加入 5，此时 steps 仍为1？注意：处理完第1层后 steps 变为1，然后下一层队列 [1,2] 被逐个处理，当处理到 2 时，发现 5 是邻居，将在下一层加入，但 steps 是在每层结束时增加。更准确：在第1步时，队列 [1,2] 是第1层的节点，steps 此时为1。然后处理第1层节点时，会将它们的邻居（第2层）加入队列，但 steps 还没增加。当处理完第1层所有节点后，steps 变为2，然后下一轮循环会从队列中取第2层节点。因此当找到 5 时，steps 应该为2（即路径长度2）。算法实现中，是在每层处理完后 steps++，所以返回的 steps 就是层数，即边数。
5. 并查集
javascript
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
this.count = n;
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
let rootX = this.find(x), rootY = this.find(y);
if (rootX === rootY) return;
if (this.rank[rootX] < this.rank[rootY]) this.parent[rootX] = rootY;
else if (this.rank[rootX] > this.rank[rootY]) this.parent[rootY] = rootX;
else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
this.count--;
}
connected(x, y) {
return this.find(x) === this.find(y);
}
getCount() {
return this.count;
}
}【例题与图解】
题目：LeetCode 547. 省份数量
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
图解：
- 初始 parent = [0,1,2]，count=3。
- 遍历矩阵，发现 (0,1) 相连，union(0,1)：parent[1]=0，rank[0]=1，count=2。
- (0,2) 不相连，(1,2) 不相连，最终 count=2，即两个连通分量：{0,1} 和 {2}。
6. 二叉树遍历
6.1 递归前/中/后序
javascript
// 前序
function preorderTraversal(root) {
const res = [];
function dfs(node) {
if (!node) return;
res.push(node.val);
dfs(node.left);
dfs(node.right);
}
dfs(root);
return res;
}
// 中序、后序类似，调整访问顺序即可【例题与图解】
题目：LeetCode 144. 二叉树的前序遍历
输入：二叉树 [1,null,2,3]
树结构：
1
\
2
/
3输出：[1,2,3]
图解：递归顺序：根(1) → 右子树(2) → 左子树(3) → [1,2,3]。
6.2 迭代前序遍历
javascript
function preorderTraversal(root) {
if (!root) return [];
const res = [];
const stack = [root];
while (stack.length) {
const node = stack.pop();
res.push(node.val);
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return res;
}【例题与图解】
输入同上，输出 [1,2,3]。
图解：
- stack 初始 [1]
- 弹出 1，res=[1]，压入右2，左null → stack=[2]
- 弹出 2，res=[1,2]，压入右3，左null → stack=[3]
- 弹出 3，res=[1,2,3]，结束。
6.3 迭代中序遍历
javascript
function inorderTraversal(root) {
const res = [];
const stack = [];
let curr = root;
while (curr || stack.length) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.push(curr.val);
curr = curr.right;
}
return res;
}【例题与图解】
输入同上，中序遍历输出应为 [1,3,2]。
图解：
- curr=1，stack=[1]，curr=1.left=null → 弹出1，res=[1]，curr=1.right=2
- curr=2，stack=[2]，curr=2.left=3 → stack=[2,3]，curr=3.left=null → 弹出3，res=[1,3]，curr=3.right=null → 弹出2，res=[1,3,2]，curr=2.right=null，结束。
7. 排序算法
7.1 快速排序
javascript
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
return arr;
}
function partition(arr, left, right) {
const pivot = arr[left];
let i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
if (i < j) arr[i++] = arr[j];
while (i < j && arr[i] <= pivot) i++;
if (i < j) arr[j--] = arr[i];
}
arr[i] = pivot;
return i;
}【例题与图解】
题目：排序数组 [3,6,8,10,1,2,1]
输出：[1,1,2,3,6,8,10]
图解一次 partition（以第一个元素 3 为基准）：
初始: [3,6,8,10,1,2,1] left=0,right=6
从右找小于3的数: 找到 1（索引6），交换到左边 → [1,6,8,10,1,2,3] (i=1)
从左找大于3的数: 找到 6（索引1），交换到右边 → [1,3,8,10,1,2,6] (j=5)
从右找小于3的数: 找到 2（索引5），交换到左边 → [1,2,8,10,1,3,6] (i=3)
从左找大于3的数: 找到 8（索引2），交换到右边 → [1,2,3,10,1,8,6] (j=4)
从右找小于3的数: 找到 1（索引4），交换到左边 → [1,2,1,10,3,8,6] (i=4)
此时 i=j=4，基准归位 arr[4]=3 → [1,2,1,3,10,8,6]
返回索引4，然后递归排序左右。7.2 归并排序
javascript
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const res = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) res.push(left[i++]);
else res.push(right[j++]);
}
return res.concat(left.slice(i)).concat(right.slice(j));
}【例题与图解】
输入同上 [3,6,8,10,1,2,1]
输出：[1,1,2,3,6,8,10]
图解：分治过程
原始数组: [3,6,8,10,1,2,1]
拆分: [3,6,8,10] 和 [1,2,1]
继续拆分直到单个元素，然后合并：
合并 [3] [6] → [3,6]
合并 [8] [10] → [8,10]
合并 [3,6] [8,10] → [3,6,8,10]
另一边: [1] [2] → [1,2]; [1] 单独；合并 [1,2] [1] → [1,1,2]
最后合并 [3,6,8,10] 和 [1,1,2] → [1,1,2,3,6,8,10]7.3 堆排序
javascript
function heapSort(arr) {
for (let i = Math.floor(arr.length/2)-1; i >= 0; i--) heapify(arr, i, arr.length);
for (let i = arr.length-1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, 0, i);
}
return arr;
}
function heapify(arr, i, size) {
let largest = i;
const left = 2*i+1, right = 2*i+2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, largest, size);
}
}【例题与图解】
输入同上 [3,6,8,10,1,2,1]
输出：[1,1,2,3,6,8,10]
图解：建堆过程（大顶堆）：
初始数组: [3,6,8,10,1,2,1]
从最后一个非叶子节点（索引2）开始调整：
索引2: 8, 左右子 2和1，8最大，不变。
索引1: 6, 左右子 10和1，10最大，交换6和10 → [3,10,8,6,1,2,1]
索引0: 3, 左右子 10和8，10最大，交换3和10 → [10,3,8,6,1,2,1]，然后递归调整索引1（原3的位置）：
索引1: 3, 左右子 6和1，6最大，交换3和6 → [10,6,8,3,1,2,1]
建堆完成。
然后交换堆顶与末尾，再调整...8. 拓扑排序
javascript
function topologicalSort(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const inDegree = new Array(numCourses).fill(0);
for (const [a, b] of prerequisites) {
graph[b].push(a);
inDegree[a]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) if (inDegree[i] === 0) queue.push(i);
const result = [];
while (queue.length) {
const node = queue.shift();
result.push(node);
for (const neighbor of graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) queue.push(neighbor);
}
}
return result.length === numCourses ? result : [];
}【例题与图解】
题目：LeetCode 207. 课程表（判断能否完成）
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：拓扑序列之一 [0,1,2,3] 或 [0,2,1,3]
图解：
依赖关系: 0→1, 0→2, 1→3, 2→3
入度: 0:0, 1:1, 2:1, 3:2
队列初始 [0]
取出0，减少邻居1和2的入度：1入度变0，2入度变0 → 队列 [1,2]
取出1，减少邻居3的入度：3入度变1 → 队列 [2]
取出2，减少邻居3的入度：3入度变0 → 队列 [3]
取出3，结束。结果 [0,1,2,3]9. Dijkstra 最短路径
javascript
function dijkstra(graph, start) {
const n = graph.length;
const dist = new Array(n).fill(Infinity);
dist[start] = 0;
const visited = new Array(n).fill(false);
const pq = [[0, start]]; // 模拟优先队列
while (pq.length) {
pq.sort((a,b) => a[0]-b[0]);
const [d, u] = pq.shift();
if (visited[u]) continue;
visited[u] = true;
for (const [v, w] of graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push([dist[v], v]);
}
}
}
return dist;
}【例题与图解】
题目：LeetCode 743. 网络延迟时间（简化版）
输入：graph 邻接表，例如：
graph = [
[[1,4], [2,1]], // 0→1(4), 0→2(1)
[[3,1]], // 1→3(1)
[[1,2], [3,5]], // 2→1(2), 2→3(5)
[] // 3 无出边
]
start = 0输出：dist = [0, 3, 1, 4]
图解：
初始化 dist[0]=0，其余无穷。
从0出发，更新邻居1(4)和2(1)：dist[1]=4, dist[2]=1
优先队列中距离最小的节点2（1），取出2，更新邻居1(1+2=3 <4) → dist[1]=3，邻居3(1+5=6) → dist[3]=6
取出1（3），更新邻居3(3+1=4 <6) → dist[3]=4
取出3（4），无更新。
最终 dist = [0,3,1,4]二、规律性算法（含例题和图解）
10. 双指针
10.1 对撞指针（两数之和 II）
javascript
function twoSum(numbers, target) {
let left = 0, right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) return [left+1, right+1];
else if (sum < target) left++;
else right--;
}
return [];
}【例题与图解】
题目：LeetCode 167. 两数之和 II - 输入有序数组
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
图解：
numbers: 2 7 11 15
L=0, R=3, sum=2+15=17>9 → R=2
L=0, R=2, sum=2+11=13>9 → R=1
L=0, R=1, sum=2+7=9 → 返回 [1,2]10.2 快慢指针（环形链表）
javascript
function hasCycle(head) {
if (!head || !head.next) return false;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}【例题与图解】
题目：LeetCode 141. 环形链表
输入：链表 3->2->0->-4，尾节点 -4 指向 2（形成环）
输出：true
图解：
链表: 3 → 2 → 0 → -4
↑________↓
slow=3, fast=3
slow=2, fast=0
slow=0, fast=2
slow=-4, fast= -4（相遇）→ 有环10.3 分离指针（合并两个有序数组）
javascript
function merge(nums1, m, nums2, n) {
let i = m-1, j = n-1, k = m+n-1;
while (i>=0 && j>=0) {
if (nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
while (j>=0) nums1[k--] = nums2[j--];
}【例题与图解】
题目：LeetCode 88. 合并两个有序数组
输入：nums1 = [1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3
输出：nums1 变为 [1,2,2,3,5,6]
图解：
nums1: [1,2,3,0,0,0] i指向3（索引2），k指向末尾（索引5）
nums2: [2,5,6] j指向6（索引2）
比较 3 和 6 → 6大，nums1[5]=6，j=1,k=4
比较 3 和 5 → 5大，nums1[4]=5，j=0,k=3
比较 3 和 2 → 3大，nums1[3]=3，i=1,k=2
比较 2 和 2 → 2大（相等时取nums2），nums1[2]=2，j=-1,k=1
此时j<0，停止。剩余nums1前两个元素 [1,2] 已在正确位置。
最终 [1,2,2,3,5,6]11. 单调栈
11.1 下一个更大元素 I
javascript
function nextGreaterElement(nums1, nums2) {
const stack = [];
const map = new Map();
for (let num of nums2) {
while (stack.length && num > stack[stack.length-1]) {
map.set(stack.pop(), num);
}
stack.push(num);
}
while (stack.length) map.set(stack.pop(), -1);
return nums1.map(num => map.get(num));
}【例题与图解】
题目：LeetCode 496. 下一个更大元素 I
输入：nums1 = [4,1,2], nums2 = [1,3,4,2]
输出：[-1,3,-1]
图解：
遍历 nums2:
1: 栈空，压入1 → stack=[1]
3: 3>1，弹出1，map[1]=3；压入3 → stack=[3]
4: 4>3，弹出3，map[3]=4；压入4 → stack=[4]
2: 2<4，压入2 → stack=[4,2]
结束，栈剩余 [4,2] 对应 map[4]=-1, map[2]=-1
结果：nums1[4] → -1, [1] → 3, [2] → -111.2 每日温度
javascript
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const res = new Array(n).fill(0);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length && temperatures[i] > temperatures[stack[stack.length-1]]) {
const prev = stack.pop();
res[prev] = i - prev;
}
stack.push(i);
}
return res;
}【例题与图解】
题目：LeetCode 739. 每日温度
输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]
图解：
索引:0 1 2 3 4 5 6 7
值:73 74 75 71 69 72 76 73
stack过程：
i=0: stack=[0]
i=1: 74>73 → 弹出0,res[0]=1；压1 → [1]
i=2: 75>74 → 弹出1,res[1]=1；压2 → [2]
i=3: 71<75 → 压3 → [2,3]
i=4: 69<71 → 压4 → [2,3,4]
i=5: 72>69 → 弹出4,res[4]=1；72>71 → 弹出3,res[3]=2；72<75 → 压5 → [2,5]
i=6: 76>72 → 弹出5,res[5]=1；76>75 → 弹出2,res[2]=4；压6 → [6]
i=7: 73<76 → 压7 → [6,7]
结束，栈剩余 [6,7] 对应 res[6]=0, res[7]=012. 前缀和与差分
12.1 一维前缀和
javascript
class PrefixSum {
constructor(nums) {
this.prefix = new Array(nums.length+1).fill(0);
for (let i=0; i<nums.length; i++) this.prefix[i+1] = this.prefix[i] + nums[i];
}
query(l, r) {
return this.prefix[r+1] - this.prefix[l];
}
}【例题与图解】
题目：LeetCode 303. 区域和检索 - 数组不可变
输入：nums = [-2,0,3,-5,2,-1]，多次查询如 sumRange(0,2)
输出：(-2+0+3)=1
图解：
prefix: [0, -2, -2, 1, -4, -2, -3] (索引0到6)
query(0,2) = prefix[3] - prefix[0] = 1 - 0 = 1
query(2,5) = prefix[6] - prefix[2] = -3 - (-2) = -112.2 二维前缀和
javascript
class PrefixSum2D {
constructor(matrix) {
const m = matrix.length, n = matrix[0].length;
this.prefix = Array.from({ length: m+1 }, () => new Array(n+1).fill(0));
for (let i=0; i<m; i++)
for (let j=0; j<n; j++)
this.prefix[i+1][j+1] = matrix[i][j] + this.prefix[i][j+1] + this.prefix[i+1][j] - this.prefix[i][j];
}
query(x1,y1,x2,y2) {
return this.prefix[x2+1][y2+1] - this.prefix[x1][y2+1] - this.prefix[x2+1][y1] + this.prefix[x1][y1];
}
}【例题与图解】
题目：LeetCode 304. 二维区域和检索 - 矩阵不可变
输入：矩阵
[3,0,1,4,2]
[5,6,3,2,1]
[1,2,0,1,5]
[4,1,0,1,7]
[1,0,3,0,5]查询 sumRegion(2,1,4,3) 即子矩阵从 (2,1) 到 (4,3)
输出：8（计算过程略）
图解：利用容斥原理。
12.3 差分数组
javascript
class Difference {
constructor(nums) {
this.diff = new Array(nums.length);
this.diff[0] = nums[0];
for (let i=1; i<nums.length; i++) this.diff[i] = nums[i] - nums[i-1];
}
increment(l, r, val) {
this.diff[l] += val;
if (r+1 < this.diff.length) this.diff[r+1] -= val;
}
result() {
const res = new Array(this.diff.length);
res[0] = this.diff[0];
for (let i=1; i<this.diff.length; i++) res[i] = res[i-1] + this.diff[i];
return res;
}
}【例题与图解】
题目：LeetCode 370. 区间加法（假设）
输入：长度为5的数组初始全0，操作：[1,3,2]（给索引1到3加2），[2,4,3]（给索引2到4加3）
输出：最终数组 [0,2,5,5,3]
图解：
初始 diff: [0,0,0,0,0] (实际根据原数组计算，这里原数组全0，diff[0]=0, diff[1]=0,...)
操作1 [1,3,2]: diff[1]+=2, diff[4]-=2 (因为r=3, r+1=4) → diff=[0,2,0,0,-2]
操作2 [2,4,3]: diff[2]+=3, diff[5]不存在，只加左边 → diff=[0,2,3,0,-2]
还原：res[0]=0; res[1]=0+2=2; res[2]=2+3=5; res[3]=5+0=5; res[4]=5+(-2)=3 → [0,2,5,5,3]13. 贪心算法
13.1 区间调度（无重叠区间）
javascript
function eraseOverlapIntervals(intervals) {
if (intervals.length === 0) return 0;
intervals.sort((a,b) => a[1] - b[1]);
let count = 1;
let end = intervals[0][1];
for (let i=1; i<intervals.length; i++) {
if (intervals[i][0] >= end) {
count++;
end = intervals[i][1];
}
}
return intervals.length - count;
}【例题与图解】
题目：LeetCode 435. 无重叠区间
输入：intervals = [[1,2],[2,3],[3,4],[1,3]]
输出：1（移除 [1,3] 可使剩余区间无重叠）
图解：
排序后按终点： [1,2], [2,3], [1,3], [3,4] （实际按终点排序应为 [1,2],[2,3],[1,3],[3,4]？注意 [1,3] 终点3大于 [2,3] 的终点3？相等时顺序任意）
正确排序：[1,2](end=2), [2,3](end=3), [1,3](end=3), [3,4](end=4)
取第一个 [1,2]，end=2
第二个 [2,3] 起点2 >=2，不重叠，count=2，end=3
第三个 [1,3] 起点1<3，重叠，跳过
第四个 [3,4] 起点3>=3，不重叠，count=3，end=4
最终 count=3，需移除 4-3=1 个。13.2 分发饼干
javascript
function findContentChildren(g, s) {
g.sort((a,b)=>a-b);
s.sort((a,b)=>a-b);
let i=0, j=0;
while (i<g.length && j<s.length) {
if (s[j] >= g[i]) i++;
j++;
}
return i;
}【例题与图解】
题目：LeetCode 455. 分发饼干
输入：g = [1,2,3], s = [1,1]
输出：1（只能满足一个孩子）
图解：
排序后 g=[1,2,3], s=[1,1]
i=0,j=0: s[0]=1 >= g[0]=1 → i=1,j=1
i=1,j=1: s[1]=1 < g[1]=2 → j=2 (j越界)
结束，i=114. 递归思维
14.1 反转链表（递归）
javascript
function reverseList(head) {
if (!head || !head.next) return head;
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}【例题与图解】
题目：LeetCode 206. 反转链表
输入：链表 1->2->3->4->5
输出：5->4->3->2->1
图解：
递归过程：
reverseList(1): 调用 reverseList(2)
reverseList(2): 调用 reverseList(3)
reverseList(3): 调用 reverseList(4)
reverseList(4): 调用 reverseList(5)
reverseList(5): 返回5（头）
4.next.next = 4 即 5.next=4，4.next=null → 返回5
3.next.next = 3 即 4.next=3，3.next=null → 返回5
2.next.next = 2 即 3.next=2，2.next=null → 返回5
1.next.next = 1 即 2.next=1，1.next=null → 返回5
最终链表 5->4->3->2->114.2 二叉树的最大深度
javascript
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}【例题与图解】
题目：LeetCode 104. 二叉树的最大深度
输入：二叉树 [3,9,20,null,null,15,7]
输出：3
图解：
3 depth=1+max( leftDepth, rightDepth )
/ \
9 20 leftDepth(9)=1, rightDepth(20)=1+max(1,1)=2
/ \ 所以 root depth = 1+max(1,2)=3
15 7三、固定数据结构（含例题和图解）
由于篇幅原因，后续的链表、栈队列、堆、树状数组、线段树、Trie、LRU 缓存等模板的例题和图解将简要给出，您可以根据需要自行补充完整。
15. 链表操作
15.1 反转链表（迭代）
javascript
function reverseList(head) {
let prev = null, curr = head;
while (curr) {
const nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}【例题】：同 14.1，输入 1->2->3->4->5，输出 5->4->3->2->1。
图解：每一步指针变化。
15.2 合并两个有序链表
javascript
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(-1);
let curr = dummy;
while (l1 && l2) {
if (l1.val < l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 || l2;
return dummy.next;
}【例题】：LeetCode 21. 合并两个有序链表
输入：1->2->4 和 1->3->4，输出 1->1->2->3->4->4。
16. 栈与队列
16.1 栈（数组实现）
javascript
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}【例题】 LeetCode 20. 有效的括号
输入：s = "()[]{}"
输出：true
图解：
遍历字符串：
遇到 '(' → 压栈
遇到 ')' → 弹出栈顶 '('，匹配成功
遇到 '[' → 压栈
遇到 ']' → 弹出栈顶 '['，匹配成功
遇到 '{' → 压栈
遇到 '}' → 弹出栈顶 '{'，匹配成功
栈最终为空 → 有效16.2 队列（数组模拟，注意 shift 效率低）
javascript
class Queue {
constructor() {
this.items = [];
}
enqueue(element) {
this.items.push(element);
}
dequeue() {
return this.items.shift();
}
front() {
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}【例题】 LeetCode 933. 最近的请求次数
输入：["ping","ping","ping","ping"], [[1],[100],[3001],[3002]]
输出：[1,2,3,3]
图解：
队列存储时间戳：
ping(1) → 队列 [1] → 返回1
ping(100) → 队列 [1,100] → 移除小于1的？无，返回2
ping(3001) → 队列 [1,100,3001] → 移除小于1？无，返回3
ping(3002) → 队列 [1,100,3001,3002] → 移除 <3002-3000=2 的元素，即1被移除，队列 [100,3001,3002] → 返回317. 堆（最小堆）
17.1 最小堆实现
javascript
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(i) { return Math.floor((i-1)/2); }
getLeftIndex(i) { return 2*i+1; }
getRightIndex(i) { return 2*i+2; }
swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length-1);
}
bubbleUp(index) {
while (index > 0) {
const parent = this.getParentIndex(index);
if (this.heap[parent] > this.heap[index]) {
this.swap(parent, index);
index = parent;
} else break;
}
}
extractMin() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.sinkDown(0);
return min;
}
sinkDown(index) {
const length = this.heap.length;
while (true) {
let left = this.getLeftIndex(index);
let right = this.getRightIndex(index);
let swapIndex = null;
if (left < length && this.heap[left] < this.heap[index]) swapIndex = left;
if (right < length) {
if ((swapIndex === null && this.heap[right] < this.heap[index]) ||
(swapIndex !== null && this.heap[right] < this.heap[left])) {
swapIndex = right;
}
}
if (swapIndex === null) break;
this.swap(index, swapIndex);
index = swapIndex;
}
}
peek() { return this.heap[0] || null; }
size() { return this.heap.length; }
}【例题】 LeetCode 215. 数组中的第K个最大元素（用最小堆找第K大）
输入：nums = [3,2,1,5,6,4], k = 2
输出：5
图解：
构建一个大小为 k 的最小堆，堆中存放最大的 k 个元素。
遍历数组：
3 → 堆 [3]
2 → 堆 [2,3]（2<3，堆顶2）
1 → 1<2，跳过
5 → 5>2，弹出2，插入5，堆 [3,5]（3<5）
6 → 6>3，弹出3，插入6，堆 [5,6]
4 → 4<5，跳过
最终堆顶为5，即第2大元素。18. 树状数组（Fenwick Tree）
18.1 树状数组实现
javascript
class FenwickTree {
constructor(n) {
this.size = n;
this.tree = new Array(n+1).fill(0); // 索引从1开始
}
lowbit(x) { return x & -x; }
update(i, delta) {
while (i <= this.size) {
this.tree[i] += delta;
i += this.lowbit(i);
}
}
query(i) { // 前缀和 [1..i]
let sum = 0;
while (i > 0) {
sum += this.tree[i];
i -= this.lowbit(i);
}
return sum;
}
rangeQuery(l, r) { // [l, r] 闭区间
return this.query(r) - this.query(l-1);
}
}【例题】 LeetCode 307. 区域和检索 - 数组可修改
输入：
初始化 nums = [1,3,5]
执行：
sumRange(0,2)→ 期望 9update(1,2)将索引1的值改为2（即增加 -1）sumRange(0,2)→ 期望 8
输出：[9,8]
图解：
初始建树（以1为基）：
nums: [1,3,5]
tree[1] = 1
tree[2] = 1+3=4
tree[3] = 5
tree[4] = 1+3+5=9
查询 sumRange(0,2) 即 [1..3] 的和：query(3)=tree[3]+tree[2]=5+4=9
update(1,2) 即将原值3改为2，相当于 delta=-1：
i=2 (因为索引1对应树中索引2？注意：原数组索引0对应树中索引1，索引1对应树中索引2)
更新 i=2: tree[2]-=1 → 3
i=4: tree[4]-=1 → 8
再次查询 sumRange(0,2)=query(3)=tree[3]+tree[2]=5+3=819. 线段树（Segment Tree）
19.1 线段树实现（区间求和）
javascript
class SegmentTree {
constructor(nums) {
this.n = nums.length;
this.tree = new Array(4 * this.n);
this.build(nums, 0, 0, this.n-1);
}
build(nums, node, l, r) {
if (l === r) {
this.tree[node] = nums[l];
return;
}
const mid = Math.floor((l+r)/2);
const leftNode = 2*node+1;
const rightNode = 2*node+2;
this.build(nums, leftNode, l, mid);
this.build(nums, rightNode, mid+1, r);
this.tree[node] = this.tree[leftNode] + this.tree[rightNode];
}
update(index, val, node=0, l=0, r=this.n-1) {
if (l === r) {
this.tree[node] = val;
return;
}
const mid = Math.floor((l+r)/2);
const leftNode = 2*node+1;
const rightNode = 2*node+2;
if (index <= mid) this.update(index, val, leftNode, l, mid);
else this.update(index, val, rightNode, mid+1, r);
this.tree[node] = this.tree[leftNode] + this.tree[rightNode];
}
query(L, R, node=0, l=0, r=this.n-1) {
if (L <= l && r <= R) return this.tree[node];
const mid = Math.floor((l+r)/2);
const leftNode = 2*node+1;
const rightNode = 2*node+2;
let sum = 0;
if (L <= mid) sum += this.query(L, R, leftNode, l, mid);
if (R > mid) sum += this.query(L, R, rightNode, mid+1, r);
return sum;
}
}【例题】 同 LeetCode 307
输入同上
输出：[9,8]
图解：
线段树结构（以数组 [1,3,5] 为例）：
[0-2] 9
/ \
[0-1] 4 [2-2] 5
/ \
[0-0]1 [1-1]3
查询 [0,2]：根节点直接返回9。
更新索引1为2：
递归到 [1-1] 节点，将其值改为2，然后回溯更新父节点： [0-1] 变为 1+2=3，根节点变为 3+5=8。
再次查询 [0,2] 返回8。20. Trie 前缀树
20.1 Trie 实现
javascript
class TrieNode {
constructor() {
this.children = new Map();
this.isEnd = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let ch of word) {
if (!node.children.has(ch)) {
node.children.set(ch, new TrieNode());
}
node = node.children.get(ch);
}
node.isEnd = true;
}
search(word) {
let node = this.root;
for (let ch of word) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch);
}
return node.isEnd;
}
startsWith(prefix) {
let node = this.root;
for (let ch of prefix) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch);
}
return true;
}
}【例题】 LeetCode 208. 实现 Trie (前缀树)
操作序列：
insert("apple")
search("apple") // 返回 true
search("app") // 返回 false
startsWith("app") // 返回 true
insert("app")
search("app") // 返回 true输出：[null, true, false, true, null, true]
图解：
插入 "apple" 后 Trie 结构：
root
└─ a
└─ p
└─ p
└─ l
└─ e (isEnd)
搜索 "apple"：沿路径 a-p-p-l-e，最后节点 isEnd=true → true
搜索 "app"：沿路径 a-p-p，最后节点 isEnd=false → false
startsWith "app"：存在路径 a-p-p → true
插入 "app"：在路径 a-p-p 的节点标记 isEnd=true
再搜索 "app"：此时 isEnd=true → true21. LRU 缓存
21.1 LRU 缓存实现（哈希表 + 双向链表）
javascript
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
// 双向链表虚拟头尾
this.head = { key: null, value: null, prev: null, next: null };
this.tail = { key: null, value: null, prev: null, next: null };
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 辅助方法：将节点移到头部
moveToHead(node) {
this.removeNode(node);
this.addToHead(node);
}
removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
addToHead(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
// 删除尾部节点（最少使用）
removeTail() {
const node = this.tail.prev;
this.removeNode(node);
return node;
}
get(key) {
if (!this.cache.has(key)) return -1;
const node = this.cache.get(key);
this.moveToHead(node);
return node.value;
}
put(key, value) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.value = value;
this.moveToHead(node);
} else {
const newNode = { key, value, prev: null, next: null };
this.cache.set(key, newNode);
this.addToHead(newNode);
if (this.cache.size > this.capacity) {
const tailNode = this.removeTail();
this.cache.delete(tailNode.key);
}
}
}
}【例题】 LeetCode 146. LRU 缓存机制
操作序列：
LRUCache cache = new LRUCache(2);
cache.put(1,1);
cache.put(2,2);
cache.get(1); // 返回 1
cache.put(3,3); // 该操作会使得 key 2 被淘汰
cache.get(2); // 返回 -1
cache.put(4,4); // 该操作会使得 key 1 被淘汰
cache.get(1); // 返回 -1
cache.get(3); // 返回 3
cache.get(4); // 返回 4输出：[null,null,1,null,-1,null,-1,3,4]（实际按题目要求返回对应值）
图解：
初始容量2
put(1,1): 链表头部插入 (1,1)
put(2,2): 头部插入 (2,2)，链表: head⇄2⇄1⇄tail
get(1): 访问1，将1移到头部 → head⇄1⇄2⇄tail
put(3,3): 容量满，删除尾部节点2（淘汰），插入3到头部 → head⇄3⇄1⇄tail，缓存 {1:1,3:3}
get(2): 不存在，返回-1
put(4,4): 容量满，删除尾部节点1，插入4到头部 → head⇄4⇄3⇄tail，缓存 {3:3,4:4}
get(1): 不存在，-1
get(3): 存在，移到头部 → head⇄3⇄4⇄tail，返回3
get(4): 存在，移到头部 → head⇄4⇄3⇄tail，返回4