主题
数组 / 链表 / 栈 / 队列 深度指南
面向 5 年经验前端/全栈工程师，覆盖底层原理、经典算法题完整实现与面试高频追问。
每个数据结构均包含：原理讲解 → ASCII 图解 → 完整可运行代码 → 复杂度分析
一、数组（Array）
1.1 JS 数组的底层实现 —— V8 的快慢数组
V8 引擎中的数组并非传统意义上的连续内存数组，而是根据使用方式在两种内部表示之间动态切换。
快数组（Fast Elements）：底层使用 C++ 数组（FixedArray），元素在内存中连续存放，通过下标直接寻址，访问速度快。适用于索引连续、密集的场景。
慢数组（Dictionary Elements）：底层使用哈希表（HashTable / NumberDictionary），以键值对存储元素。适用于稀疏数组，避免浪费大量内存。
快数组 (Fast Elements)
┌─────────────────────────────────────────┐
│ FixedArray (连续内存) │
│ [0] [1] [2] [3] [4] [5] [6] [7] │
│ 10 20 30 40 50 60 70 80 │
└─────────────────────────────────────────┘
→ 下标访问 O(1)，缓存友好
慢数组 (Dictionary Elements)
┌─────────────────────────────────────────┐
│ HashTable │
│ { 0: 10, 100: 20, 99999: 30 } │
└─────────────────────────────────────────┘
→ 稀疏场景节省内存，访问需要哈希计算切换时机：
| 方向 | 条件 |
|---|---|
| 快 → 慢 | 新增元素导致需要的 FixedArray 容量 ≥ 3 × 实际元素数量（即空洞率过高） |
| 快 → 慢 | 数组索引超过 1024 且空洞超过 capacity - length - 1024 |
| 慢 → 快 | 补全所有空洞后所需的 FixedArray 空间 ≤ 50KB |
js
const fast = [1, 2, 3, 4, 5]
fast[10000] = 1
const slow = new Array(100000)
slow[0] = 1
slow[99999] = 21.2 常用方法时间复杂度
| 方法 | 时间复杂度 | 原因 |
|---|---|---|
push(x) | O(1) 均摊 | 在尾部追加，偶尔触发扩容（2倍增长）需 O(n) 拷贝 |
pop() | O(1) | 移除尾部元素 |
unshift(x) | O(n) | 在头部插入，所有元素后移 |
shift() | O(n) | 移除头部元素，所有元素前移 |
splice(i, k) | O(n) | 从索引 i 处删除/插入，后续元素需要移动 |
indexOf(x) | O(n) | 线性扫描 |
arr[i] | O(1) | 快数组直接下标寻址 |
push(6): unshift(0):
[1, 2, 3, 4, 5, _] [_, 1, 2, 3, 4, 5]
↑ 直接放 ↑ 所有元素右移一位
→ O(1) → O(n)1.3 双指针技巧
1.3.1 原地去重（LeetCode 26）
题目描述：给定一个升序排列的数组 nums，请原地删除重复元素，使每个元素只出现一次，返回删除后数组的新长度。
思路分析：使用快慢指针。慢指针 slow 指向当前不重复序列的末尾，快指针 fast 向前扫描，遇到与 slow 不同的值就将其放到 slow + 1 的位置。
初始: [1, 1, 2, 2, 3]
s
f
步骤1: nums[f]=1 === nums[s]=1 → f++
[1, 1, 2, 2, 3]
s f
步骤2: nums[f]=2 !== nums[s]=1 → s++, nums[s]=nums[f]
[1, 2, 2, 2, 3]
s f
步骤3: nums[f]=2 === nums[s]=2 → f++
[1, 2, 2, 2, 3]
s f
步骤4: nums[f]=3 !== nums[s]=2 → s++, nums[s]=nums[f]
[1, 2, 3, 2, 3]
s f
结果: 返回 s+1 = 3，前3个元素 [1, 2, 3]typescript
function removeDuplicates(nums: number[]): number {
if (nums.length === 0) return 0
let slow = 0
for (let fast = 1; fast < nums.length; fast++) {
if (nums[fast] !== nums[slow]) {
slow++
nums[slow] = nums[fast]
}
}
return slow + 1
}复杂度：时间 O(n)，空间 O(1)
1.3.2 三数之和（LeetCode 15）
题目描述：给定一个整数数组 nums，找出所有和为 0 的不重复三元组 [nums[i], nums[j], nums[k]]（i ≠ j ≠ k）。
思路分析：先排序，然后固定一个数 nums[i]，用双指针在 [i+1, n-1] 区间找两数之和为 -nums[i] 的组合。跳过重复值以去重。
排序后: [-4, -1, -1, 0, 1, 2]
固定 i=0, nums[i]=-4, target=4
L=1, R=5: -1+2=1 < 4 → L++
L=2, R=5: -1+2=1 < 4 → L++
L=3, R=5: 0+2=2 < 4 → L++
L=4, R=5: 1+2=3 < 4 → L++
L=5 >= R → 结束
固定 i=1, nums[i]=-1, target=1
L=2, R=5: -1+2=1 === target → 记录 [-1,-1,2], L++, R--
L=3, R=4: 0+1=1 === target → 记录 [-1,0,1], L++, R--
L=4 >= R → 结束
固定 i=2, nums[i]=-1 === nums[i-1] → 跳过（去重）
结果: [[-1,-1,2], [-1,0,1]]typescript
function threeSum(nums: number[]): number[][] {
const result: number[][] = []
nums.sort((a, b) => a - b)
for (let i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break
if (i > 0 && nums[i] === nums[i - 1]) continue
let left = i + 1
let right = nums.length - 1
while (left < right) {
const sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]])
while (left < right && nums[left] === nums[left + 1]) left++
while (left < right && nums[right] === nums[right - 1]) right--
left++
right--
} else if (sum < 0) {
left++
} else {
right--
}
}
}
return result
}复杂度：时间 O(n²)，空间 O(log n)（排序栈空间）
1.4 滑动窗口 —— 最长无重复子串（LeetCode 3）
题目描述：给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。
思路分析：维护一个窗口 [left, right]，用 Map 记录每个字符最后出现的索引。当 right 遇到窗口内已有的字符时，将 left 跳到该字符上次出现位置的下一位。
s = "abcabcbb"
步骤 窗口 Map maxLen
─────────────────────────────────────────────────────
right=0 [a] {a:0} 1
right=1 [a,b] {a:0, b:1} 2
right=2 [a,b,c] {a:0, b:1, c:2} 3
right=3 a重复!
left=0+1=1
[b,c,a] {a:3, b:1, c:2} 3
right=4 b重复!
left=1+1=2
[c,a,b] {a:3, b:4, c:2} 3
right=5 c重复!
left=2+1=3
[a,b,c] {a:3, b:4, c:5} 3
right=6 b重复!
left=4+1=5
[c,b] {a:3, b:6, c:5} 3
right=7 b重复!
left=6+1=7
[b] {a:3, b:7, c:5} 3
结果: 3 (对应 "abc")typescript
function lengthOfLongestSubstring(s: string): number {
const map = new Map<string, number>()
let maxLen = 0
let left = 0
for (let right = 0; right < s.length; right++) {
if (map.has(s[right]) && map.get(s[right])! >= left) {
left = map.get(s[right])! + 1
}
map.set(s[right], right)
maxLen = Math.max(maxLen, right - left + 1)
}
return maxLen
}复杂度：时间 O(n)，空间 O(min(n, m))，m 为字符集大小
二、链表（Linked List）
2.1 单链表节点定义
┌──────┬──────┐ ┌──────┬──────┐ ┌──────┬──────┐
│ val │ next │────▶│ val │ next │────▶│ val │ next │────▶ null
└──────┴──────┘ └──────┴──────┘ └──────┴──────┘
Node 1 Node 2 Node 3typescript
class ListNode {
val: number
next: ListNode | null
constructor(val: number = 0, next: ListNode | null = null) {
this.val = val
this.next = next
}
}2.2 基本操作
插入
在节点 A 后插入节点 X:
Before: A ──────────▶ B
After: A ──▶ X ──▶ B
X.next = A.next // X 先指向 B
A.next = X // A 再指向 X删除
删除节点 B (已知前驱 A):
Before: A ──▶ B ──▶ C
After: A ──────────▶ C
A.next = B.next // A 直接指向 C查找
typescript
function findNode(head: ListNode | null, target: number): ListNode | null {
let curr = head
while (curr !== null) {
if (curr.val === target) return curr
curr = curr.next
}
return null
}| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 按索引访问 | O(n) | 需要从头遍历 |
| 头部插入/删除 | O(1) | 直接操作头指针 |
| 尾部插入（无尾指针） | O(n) | 需遍历到尾部 |
| 已知前驱节点的插入/删除 | O(1) | 修改指针 |
2.3 反转链表（LeetCode 206）
题目描述：给定单链表的头节点 head，将链表反转并返回新的头节点。
思路分析（迭代）：使用三个指针 prev、curr、next。逐个翻转指针方向。
初始: null ← prev curr → 1 → 2 → 3 → null
步骤1: next = curr.next
null ← prev curr → 1 next → 2 → 3 → null
步骤2: curr.next = prev
null ← 1 ← curr next → 2 → 3 → null
步骤3: prev = curr, curr = next
null ← 1 ← prev curr → 2 → 3 → null
步骤4: 重复...
null ← 1 ← 2 ← prev curr → 3 → null
步骤5: 重复...
null ← 1 ← 2 ← 3 ← prev curr → null
curr === null，返回 prev
结果: 3 → 2 → 1 → null迭代实现：
typescript
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null
let curr = head
while (curr !== null) {
const next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
}递归实现：
递归展开:
reverseList(1→2→3→null)
reverseList(2→3→null)
reverseList(3→null)
return 3 ← 递归到底，3 是新头节点
回溯: head=2, head.next=3
3.next = 2 ← 让 3 指向 2
2.next = null ← 断开 2 的原指向
return 3
回溯: head=1, head.next=2
2.next = 1 ← 让 2 指向 1
1.next = null ← 断开 1 的原指向
return 3
结果: 3→2→1→nulltypescript
function reverseListRecursive(head: ListNode | null): ListNode | null {
if (head === null || head.next === null) return head
const newHead = reverseListRecursive(head.next)
head.next.next = head
head.next = null
return newHead
}复杂度：迭代 — 时间 O(n)，空间 O(1)；递归 — 时间 O(n)，空间 O(n)
2.4 合并两个有序链表（LeetCode 21）
题目描述：将两个升序链表合并为一个新的升序链表并返回。
思路分析：使用哨兵节点 dummy 简化边界处理，双指针逐一比较取较小值。
l1: 1 → 3 → 5
l2: 2 → 4 → 6
dummy → ?
比较 1 vs 2 → 取 1: dummy → 1
比较 3 vs 2 → 取 2: dummy → 1 → 2
比较 3 vs 4 → 取 3: dummy → 1 → 2 → 3
比较 5 vs 4 → 取 4: dummy → 1 → 2 → 3 → 4
比较 5 vs 6 → 取 5: dummy → 1 → 2 → 3 → 4 → 5
l1 为空 → 接上 l2: dummy → 1 → 2 → 3 → 4 → 5 → 6
返回 dummy.nexttypescript
function mergeTwoLists(
l1: ListNode | null,
l2: ListNode | null
): ListNode | null {
const dummy = new ListNode(-1)
let curr = dummy
while (l1 !== null && l2 !== null) {
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
}复杂度：时间 O(n + m)，空间 O(1)
2.5 环形链表检测（LeetCode 141 / 142）
题目描述：
- 141：判断链表中是否有环。
- 142：返回环的入口节点。
思路分析：Floyd 判圈算法（快慢指针）。快指针每次走 2 步，慢指针每次走 1 步。若存在环，两者必定在环内相遇。
┌───────────────────────┐
▼ │
1 → 2 → 3 → 4 → 5 → 6 → 7 ──┘
↑ 入口 (index=1)
快慢指针运动:
step slow fast
0 1 1
1 2 3
2 3 5
3 4 7
4 5 4 (环内)
5 6 6 ← 相遇!
找入口 (142):
设 head 到入口距离 = a
入口到相遇点距离 = b
相遇点到入口距离 = c (环剩余)
慢走了: a + b
快走了: a + b + n(b + c) (n 为快指针多绕的圈数)
快 = 2 × 慢: a + b + n(b+c) = 2(a + b)
化简: a = (n-1)(b+c) + c
即: 从 head 走 a 步 = 从相遇点走 c + 若干整圈
→ 一个指针从 head 出发，一个从相遇点出发，
每次各走 1 步，相遇处即为入口141 — 判断是否有环：
typescript
function hasCycle(head: ListNode | null): boolean {
let slow = head
let fast = head
while (fast !== null && fast.next !== null) {
slow = slow!.next
fast = fast.next.next
if (slow === fast) return true
}
return false
}142 — 找环入口：
typescript
function detectCycle(head: ListNode | null): ListNode | null {
let slow = head
let fast = head
while (fast !== null && fast.next !== null) {
slow = slow!.next
fast = fast.next.next
if (slow === fast) {
let ptr = head
while (ptr !== slow) {
ptr = ptr!.next
slow = slow!.next
}
return ptr
}
}
return null
}复杂度：时间 O(n)，空间 O(1)
2.6 删除链表的倒数第 N 个节点（LeetCode 19）
题目描述：给定链表，删除其倒数第 n 个节点，返回链表的头节点。
思路分析：快指针先走 n 步，然后快慢指针同步走。当快指针到达末尾时，慢指针恰好在倒数第 n+1 个节点（待删除节点的前驱）。使用 dummy 节点避免删除头节点的边界问题。
链表: 1 → 2 → 3 → 4 → 5, n=2
Step 1: fast 先走 n=2 步
dummy → 1 → 2 → 3 → 4 → 5 → null
s f
Step 2: 同步走直到 fast.next === null
dummy → 1 → 2 → 3 → 4 → 5 → null
s f
Step 3: 删除 slow.next
slow.next = slow.next.next
dummy → 1 → 2 → 3 → 5 → null
返回 dummy.nexttypescript
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head)
let fast: ListNode | null = dummy
let slow: ListNode | null = dummy
for (let i = 0; i <= n; i++) {
fast = fast!.next
}
while (fast !== null) {
fast = fast.next
slow = slow!.next
}
slow!.next = slow!.next!.next
return dummy.next
}复杂度：时间 O(n)，空间 O(1)
2.7 相交链表（LeetCode 160）
题目描述：给定两个链表的头节点 headA 和 headB，找出两个链表相交的起始节点。如果不相交返回 null。
思路分析：指针 A 遍历完链表 A 后接到链表 B 头部继续走，指针 B 同理。两者走过的总路程相同（lenA + lenB），若相交则必在交点相遇，否则同时到达 null。
A: a1 → a2 ↘
c1 → c2 → c3
B: b1 → b2 → b3 ↗
A 的路径: a1 → a2 → c1 → c2 → c3 → b1 → b2 → b3 → [c1]
B 的路径: b1 → b2 → b3 → c1 → c2 → c3 → a1 → a2 → [c1]
↑ 相遇!
路程: A走了 (2+3) + 3 = 8 步
B走了 (3+3) + 2 = 8 步 → 同步到达 c1typescript
function getIntersectionNode(
headA: ListNode | null,
headB: ListNode | null
): ListNode | null {
let pA = headA
let pB = headB
while (pA !== pB) {
pA = pA === null ? headB : pA.next
pB = pB === null ? headA : pB.next
}
return pA
}复杂度：时间 O(n + m)，空间 O(1)
三、栈（Stack）
3.1 用数组实现栈
栈的操作示意 (LIFO — Last In, First Out):
push(1) push(2) push(3) pop() peek()
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ │ │ │ │ 3 │ ← │ │ │ │
│ │ │ 2 │ │ 2 │ │ 2 │ ← │ 2 │ ← 返回2
│ 1 │ │ 1 │ │ 1 │ │ 1 │ │ 1 │ (不弹出)
└───┘ └───┘ └───┘ └───┘ └───┘typescript
class Stack<T> {
private items: T[] = []
push(val: T): void {
this.items.push(val)
}
pop(): T | undefined {
return this.items.pop()
}
peek(): T | undefined {
return this.items[this.items.length - 1]
}
isEmpty(): boolean {
return this.items.length === 0
}
size(): number {
return this.items.length
}
}所有操作均为 O(1)。
3.2 有效括号（LeetCode 20）
题目描述：给定一个只包含 ()、{}、[] 的字符串，判断字符串是否有效。有效条件：左括号必须用相同类型的右括号闭合，且闭合顺序正确。
思路分析：遍历字符串，遇到左括号入栈，遇到右括号弹出栈顶检查是否匹配。
s = "{[()]}"
字符 操作 栈
──────────────────────────
{ push '}' ['}']
[ push ']' ['}', ']']
( push ')' ['}', ']', ')']
) pop → ')' ['}', ']'] ✓ 匹配
] pop → ']' ['}'] ✓ 匹配
} pop → '}' [] ✓ 匹配
栈为空 → 返回 truetypescript
function isValid(s: string): boolean {
const stack: string[] = []
const map: Record<string, string> = {
'(': ')',
'[': ']',
'{': '}'
}
for (const ch of s) {
if (map[ch]) {
stack.push(map[ch])
} else {
if (stack.pop() !== ch) return false
}
}
return stack.length === 0
}复杂度：时间 O(n)，空间 O(n)
3.3 最小栈（LeetCode 155）
题目描述：设计一个支持 push、pop、top、getMin 操作的栈，且 getMin 在 O(1) 时间内返回栈内最小元素。
思路分析：使用辅助栈同步记录每个状态下的最小值。每次 push 时，辅助栈压入 min(当前值, 辅助栈顶)。
操作 主栈 辅助栈(最小值)
─────────────────────────────────────────
push(-2) [-2] [-2]
push(0) [-2, 0] [-2, -2]
push(-3) [-2, 0, -3] [-2, -2, -3]
getMin() → -3
pop() [-2, 0] [-2, -2]
top() → 0
getMin() → -2typescript
class MinStack {
private stack: number[] = []
private minStack: number[] = []
push(val: number): void {
this.stack.push(val)
const min = this.minStack.length === 0
? val
: Math.min(val, this.minStack[this.minStack.length - 1])
this.minStack.push(min)
}
pop(): void {
this.stack.pop()
this.minStack.pop()
}
top(): number {
return this.stack[this.stack.length - 1]
}
getMin(): number {
return this.minStack[this.minStack.length - 1]
}
}复杂度：所有操作时间 O(1)，空间 O(n)
3.4 单调栈原理与应用
单调栈：栈内元素保持单调递增（或递减）的顺序。新元素入栈前，弹出所有破坏单调性的栈顶元素。弹出时意味着找到了这些元素的"下一个更大/更小值"。
单调递减栈示意（栈底 → 栈顶 递减）:
元素依次入栈: 5, 3, 1, 4
push 5 → [5]
push 3 → [5, 3] 3 < 5 ✓ 单调
push 1 → [5, 3, 1] 1 < 3 ✓ 单调
push 4 → 4 > 1 → pop 1 1 的下一个更大元素 = 4
4 > 3 → pop 3 3 的下一个更大元素 = 4
4 < 5 ✓
[5, 4]3.4.1 每日温度（LeetCode 739）
题目描述：给定一个温度数组 temperatures，对于每一天，求至少要等多少天才能遇到更高的温度。如果之后不会更高则为 0。
思路分析：维护一个单调递减栈（存索引）。遍历到新温度时，若比栈顶温度高，则弹出栈顶并计算天数差。
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
i=0: 73 栈=[] push 0 栈=[0]
i=1: 74>73 pop 0 ans[0]=1-0=1 栈=[]
push 1 栈=[1]
i=2: 75>74 pop 1 ans[1]=2-1=1 栈=[]
push 2 栈=[2]
i=3: 71<75 push 3 栈=[2,3]
i=4: 69<71 push 4 栈=[2,3,4]
i=5: 72>69 pop 4 ans[4]=5-4=1
72>71 pop 3 ans[3]=5-3=2
72<75 push 5 栈=[2,5]
i=6: 76>72 pop 5 ans[5]=6-5=1
76>75 pop 2 ans[2]=6-2=4
push 6 栈=[6]
i=7: 73<76 push 7 栈=[6,7]
结果: [1, 1, 4, 2, 1, 1, 0, 0]typescript
function dailyTemperatures(temperatures: number[]): number[] {
const n = temperatures.length
const answer = new Array(n).fill(0)
const stack: number[] = []
for (let i = 0; i < n; i++) {
while (
stack.length > 0 &&
temperatures[i] > temperatures[stack[stack.length - 1]]
) {
const j = stack.pop()!
answer[j] = i - j
}
stack.push(i)
}
return answer
}复杂度：时间 O(n)（每个元素最多入栈出栈各一次），空间 O(n)
3.4.2 下一个更大元素 I（LeetCode 496）
题目描述：给定两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对于 nums1 中的每个元素，找到它在 nums2 中的下一个更大元素。如果不存在则返回 -1。
思路分析：先用单调栈对 nums2 求出每个元素的下一个更大元素存入 Map，再对 nums1 查表。
nums1 = [4,1,2], nums2 = [1,3,4,2]
对 nums2 建立单调递减栈:
i=0: 1 栈=[] push 1 栈=[1]
i=1: 3>1 pop 1 map[1]=3 栈=[]
push 3 栈=[3]
i=2: 4>3 pop 3 map[3]=4 栈=[]
push 4 栈=[4]
i=3: 2<4 push 2 栈=[4,2]
栈中剩余 4,2 → map[4]=-1, map[2]=-1
查询 nums1: [map[4], map[1], map[2]] = [-1, 3, -1]typescript
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
const map = new Map<number, number>()
const stack: number[] = []
for (const num of nums2) {
while (stack.length > 0 && num > stack[stack.length - 1]) {
map.set(stack.pop()!, num)
}
stack.push(num)
}
while (stack.length > 0) {
map.set(stack.pop()!, -1)
}
return nums1.map(n => map.get(n)!)
}复杂度：时间 O(n + m)，空间 O(n)
四、队列（Queue）
4.1 用数组实现队列
队列操作示意 (FIFO — First In, First Out):
enqueue(1) enqueue(2) enqueue(3) dequeue()
┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│ 1 │ │ 1 2 │ │ 1 2 3 │ │ 2 3 │
└─────────┘ └─────────┘ └─────────┘ └─────────┘
front=1 front=1 front=1 front=2
rear=2 rear=3 rear=3typescript
class Queue<T> {
private items: T[] = []
enqueue(val: T): void {
this.items.push(val)
}
dequeue(): T | undefined {
return this.items.shift()
}
front(): T | undefined {
return this.items[0]
}
isEmpty(): boolean {
return this.items.length === 0
}
size(): number {
return this.items.length
}
}注意：
shift()是 O(n) 操作。生产环境如需高性能队列，应使用链表实现或环形缓冲区。
4.2 用链表实现队列（O(1) 出队）
typescript
class LinkedListQueue<T> {
private head: { val: T; next: any } | null = null
private tail: { val: T; next: any } | null = null
private _size = 0
enqueue(val: T): void {
const node = { val, next: null }
if (this.tail) {
this.tail.next = node
} else {
this.head = node
}
this.tail = node
this._size++
}
dequeue(): T | undefined {
if (!this.head) return undefined
const val = this.head.val
this.head = this.head.next
if (!this.head) this.tail = null
this._size--
return val
}
front(): T | undefined {
return this.head?.val
}
isEmpty(): boolean {
return this._size === 0
}
size(): number {
return this._size
}
}4.3 双端队列（Deque）
双端队列两端都可以进行插入和删除操作：
┌──── addFront
▼
┌──┬──┬──┬──┬──┐
│ │ │ │ │ │
└──┴──┴──┴──┴──┘
▲ ▲
│ │
removeFront addRear / removeReartypescript
class Deque<T> {
private items: T[] = []
addFront(val: T): void {
this.items.unshift(val)
}
addRear(val: T): void {
this.items.push(val)
}
removeFront(): T | undefined {
return this.items.shift()
}
removeRear(): T | undefined {
return this.items.pop()
}
peekFront(): T | undefined {
return this.items[0]
}
peekRear(): T | undefined {
return this.items[this.items.length - 1]
}
isEmpty(): boolean {
return this.items.length === 0
}
size(): number {
return this.items.length
}
}4.4 滑动窗口最大值（LeetCode 239）
题目描述：给定一个整数数组 nums 和滑动窗口大小 k，窗口从最左端滑动到最右端，每次滑动一位。返回每个窗口位置的最大值。
思路分析：使用单调递减双端队列（存索引）。队头始终是当前窗口的最大值索引。每次滑动时：
- 移除队头已滑出窗口的索引
- 从队尾移除所有小于当前元素的索引（它们不可能成为最大值）
- 当前索引入队
- 窗口形成后（
i >= k - 1），队头即为当前窗口最大值
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
i=0: num=1 deque=[]
push 0 deque=[0]
i=1: num=3 3>1 → pop 0
push 1 deque=[1]
i=2: num=-1 -1<3
push 2 deque=[1,2]
i>=2 → ans.push(nums[1]) ans=[3]
i=3: num=-3 -3<-1
push 3 deque=[1,2,3]
i>=2 → ans.push(nums[1]) ans=[3,3]
i=4: num=5 检查队头: 1 >= 4-3+1=2? → 否(1<2) → pop front
deque=[2,3]
5>-3 → pop 3
5>-1 → pop 2
push 4 deque=[4]
i>=2 → ans.push(nums[4]) ans=[3,3,5]
i=5: num=3 3<5
push 5 deque=[4,5]
i>=2 → ans.push(nums[4]) ans=[3,3,5,5]
i=6: num=6 6>3 → pop 5
6>5 → pop 4
push 6 deque=[6]
i>=2 → ans.push(nums[6]) ans=[3,3,5,5,6]
i=7: num=7 7>6 → pop 6
push 7 deque=[7]
i>=2 → ans.push(nums[7]) ans=[3,3,5,5,6,7]
结果: [3, 3, 5, 5, 5, 6, 7]typescript
function maxSlidingWindow(nums: number[], k: number): number[] {
const deque: number[] = []
const result: number[] = []
for (let i = 0; i < nums.length; i++) {
while (deque.length > 0 && deque[0] < i - k + 1) {
deque.shift()
}
while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop()
}
deque.push(i)
if (i >= k - 1) {
result.push(nums[deque[0]])
}
}
return result
}复杂度：时间 O(n)（每个元素最多入队出队各一次），空间 O(k)
五、面试题精选（5 道，带详细解答）
面试题 1：用两个栈实现队列（LeetCode 232）
题目描述：请仅使用两个栈实现先入先出（FIFO）队列。
思路分析：使用 inStack 负责入队，outStack 负责出队。当 outStack 为空需要出队时，将 inStack 的所有元素逐个弹出压入 outStack，顺序自动翻转。
push(1), push(2), push(3):
inStack outStack
┌───┐ ┌───┐
│ 3 │ │ │
│ 2 │ │ │
│ 1 │ │ │
└───┘ └───┘
pop() → outStack 为空，倒入:
inStack outStack
┌───┐ ┌───┐
│ │ │ 1 │ ← pop → 返回 1
│ │ │ 2 │
│ │ │ 3 │
└───┘ └───┘
push(4), pop():
inStack outStack
┌───┐ ┌───┐
│ 4 │ │ 2 │ ← pop → 返回 2
│ │ │ 3 │
└───┘ └───┘typescript
class MyQueue {
private inStack: number[] = []
private outStack: number[] = []
push(x: number): void {
this.inStack.push(x)
}
pop(): number {
this.move()
return this.outStack.pop()!
}
peek(): number {
this.move()
return this.outStack[this.outStack.length - 1]
}
empty(): boolean {
return this.inStack.length === 0 && this.outStack.length === 0
}
private move(): void {
if (this.outStack.length === 0) {
while (this.inStack.length > 0) {
this.outStack.push(this.inStack.pop()!)
}
}
}
}复杂度：push O(1)，pop/peek 均摊 O(1)，空间 O(n)
面试题 2：用栈实现括号匹配的最大嵌套深度（LeetCode 1614）
题目描述：给定一个合法的括号字符串 s（可能包含数字和运算符），返回括号的最大嵌套深度。
思路分析：不需要真正用栈存储，只需维护一个计数器 depth。遇到 ( 则 depth++，遇到 ) 则 depth--，过程中记录最大值。
s = "(1+(2*3)+((8)/4))+1"
字符: ( 1 + ( 2 * 3 ) + ( ( 8 ) / 4 ) ) + 1
depth: 1 2 1 2 3 2 1 0
最大深度 = 3typescript
function maxDepth(s: string): number {
let depth = 0
let max = 0
for (const ch of s) {
if (ch === '(') {
depth++
max = Math.max(max, depth)
} else if (ch === ')') {
depth--
}
}
return max
}复杂度：时间 O(n)，空间 O(1)
面试题 3：旋转数组（LeetCode 189）
题目描述：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置。
思路分析：三次翻转法。先整体翻转，再翻转前 k 个，最后翻转后 n-k 个。
nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Step 1: 整体翻转 [7, 6, 5, 4, 3, 2, 1]
Step 2: 翻转前 k=3 个 [5, 6, 7, 4, 3, 2, 1]
Step 3: 翻转后 n-k 个 [5, 6, 7, 1, 2, 3, 4]typescript
function rotate(nums: number[], k: number): void {
k = k % nums.length
const reverse = (arr: number[], start: number, end: number) => {
while (start < end) {
;[arr[start], arr[end]] = [arr[end], arr[start]]
start++
end--
}
}
reverse(nums, 0, nums.length - 1)
reverse(nums, 0, k - 1)
reverse(nums, k, nums.length - 1)
}复杂度：时间 O(n)，空间 O(1)
面试题 4：LRU 缓存（LeetCode 146）
题目描述：设计一个 LRU（最近最少使用）缓存机制，支持 get 和 put 操作，均为 O(1) 时间复杂度。
思路分析：使用哈希表 + 双向链表。哈希表用于 O(1) 查找，双向链表用于 O(1) 插入和删除以维护访问顺序。在 JS 中可以直接利用 Map（保留插入顺序）来实现。
容量 capacity = 3
put(1,A) → [1:A]
put(2,B) → [1:A, 2:B]
put(3,C) → [1:A, 2:B, 3:C]
get(1) → [2:B, 3:C, 1:A] // 1 被访问，移到末尾
put(4,D) → [3:C, 1:A, 4:D] // 容量满，淘汰最久未用的 2
get(2) → -1 // 2 已被淘汰
双向链表示意:
head ↔ [2:B] ↔ [3:C] ↔ [1:A] ↔ tail
最久未用 最近使用typescript
class LRUCache {
private capacity: number
private cache: Map<number, number>
constructor(capacity: number) {
this.capacity = capacity
this.cache = new Map()
}
get(key: number): number {
if (!this.cache.has(key)) return -1
const val = this.cache.get(key)!
this.cache.delete(key)
this.cache.set(key, val)
return val
}
put(key: number, value: number): void {
if (this.cache.has(key)) {
this.cache.delete(key)
} else if (this.cache.size >= this.capacity) {
const oldestKey = this.cache.keys().next().value!
this.cache.delete(oldestKey)
}
this.cache.set(key, value)
}
}复杂度：get/put 均 O(1)，空间 O(capacity)
面试题 5：扁平化嵌套列表迭代器（LeetCode 341）
题目描述：给定一个嵌套的整数列表 nestedList，每个元素要么是整数，要么是一个列表（元素同样是整数或列表）。实现一个迭代器来展开它。
思路分析：利用栈进行 DFS。初始化时将列表逆序压入栈中（保证正序输出）。调用 hasNext 时不断检查栈顶：若栈顶是列表，则展开（逆序压栈）；若是整数则直接可用。
输入: [[1,1], 2, [1,1]]
初始化（逆序压栈）:
栈 = [[1,1], 2, [1,1]] (bottom → top)
即 top = [1,1]
hasNext():
top = [1,1] → 是列表 → 展开逆序压栈
栈 = [[1,1], 2, 1, 1]
top = 1 → 是整数 ✓
next() → 1
next() → 1
hasNext():
top = 2 → 是整数 ✓
next() → 2
hasNext():
top = [1,1] → 展开
栈 = [1, 1]
next() → 1
next() → 1
输出: [1, 1, 2, 1, 1]typescript
interface NestedInteger {
isInteger(): boolean
getInteger(): number | null
getList(): NestedInteger[]
}
class NestedIterator {
private stack: NestedInteger[]
constructor(nestedList: NestedInteger[]) {
this.stack = [...nestedList].reverse()
}
hasNext(): boolean {
while (this.stack.length > 0) {
const top = this.stack[this.stack.length - 1]
if (top.isInteger()) return true
this.stack.pop()
const list = top.getList()
for (let i = list.length - 1; i >= 0; i--) {
this.stack.push(list[i])
}
}
return false
}
next(): number {
return this.stack.pop()!.getInteger()!
}
}复杂度：next() 和 hasNext() 均摊 O(1)，空间 O(n)（n 为所有整数个数）
六、追问思考（5 道）
追问思考
为什么 JavaScript 的
Array.prototype.sort()在 V8 中从快排改为了 TimSort？ TimSort 在什么场景下优于快排？对部分有序数据的时间复杂度是多少？链表题中的"哨兵节点（dummy node）"本质上解决了什么问题？ 除了简化头节点操作外，在哪些场景下你会主动引入哨兵节点？试分析不使用哨兵节点时反转链表的边界 case 有几种。
单调栈只能解决"下一个更大元素"类问题吗？ 如果要求"上一个更小元素"该如何调整？尝试用单调栈解决 LeetCode 84（柱状图中最大的矩形）并分析为什么需要在数组两端各添加一个高度为 0 的哨兵。
LRU 缓存的 Map 实现依赖了 ES6 Map 的插入有序特性。 如果面试官要求你不使用 Map，而是用普通对象 + 手写双向链表实现，链表节点应包含哪些字段？如何做到 get/put 都严格 O(1)？
滑动窗口最大值（LeetCode 239）中的单调队列操作
deque.shift()在数组实现下是 O(n) 的。 如何将其优化为严格 O(1)？比较使用链表双端队列 vs 环形缓冲区 vs 维护 head 指针偏移量这三种方案的优劣。
数据结构对比总结
| 数据结构 | 随机访问 | 头部插入/删除 | 尾部插入/删除 | 查找 | 适用场景 |
|---|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(1) 均摊 | O(n) | 随机访问频繁、已知大小 |
| 链表 | O(n) | O(1) | O(1)* | O(n) | 频繁插入删除、大小不确定 |
| 栈 | — | — | O(1) | — | 括号匹配、DFS、撤销操作 |
| 队列 | — | O(1)** | O(1) | — | BFS、任务调度、缓冲 |
* 需维护尾指针 ** 链表实现下