刷题记录帖子

Myron2017

LC 3834. Merge Adjacent Equal Elements

我挺喜欢这道题目的，考差了用 stack 来模拟 merge 的过程。考察目的明确清晰，代码简单，但是思考过程，考察了用数据结构解决实际问题的能力。

需要注意，stack pop 出来，再插入的时候，需要继续判断是不是会有可以 merge 的情况。

class Solution:
def mergeAdjacent(self, nums: List[int]) -> List[int]:
# using stack
stack = []
for num in nums:
if not stack or stack[-1] != num:
stack.append(num)
else: # stack[-1] == num
curr = num
while stack and stack[-1] == curr:
stack.pop()
curr *= 2
stack.append(curr)
return stack

复制代码

Myron2017

LC 239. Sliding Window Maximum

如何在滑动窗口中，高效维护 min 和 max

下面我把它讲成一个可以直接背下来、面试时自动触发的“肌肉记忆”版本。

一、为什么普通办法不行？

在滑动窗口里：

窗口每次右移一格

min / max 会被加入、被删除

如果你每次都 min(window) / max(window)

👉 时间复杂度是 O(n²)（直接 TLE）

所以我们要的是：

插入 O(1)，删除 O(1)，查询 min / max O(1)

二、答案：单调队列（Monotonic Deque）
核心思想一句话

队列里只保留“将来可能成为 min / max 的元素”

无用的，提前踢掉。

三、维护 max：单调递减队列
规则

队列里：从大到小

队首：当前窗口的最大值

新元素进来时：

把比它小的全部从队尾删掉（它们永远没机会当 max 了）

代码模板

while maxdq and nums[maxdq[-1]] <= nums[r]:
maxdq.pop()
maxdq.append(r)

复制代码

四、维护 min：单调递增队列
规则

队列里：从小到大

队首：当前窗口的最小值

新元素进来时：

把比它大的全部从队尾删掉

代码模板

while mindq and nums[mindq[-1]] >= nums[r]:
mindq.pop()
mindq.append(r)

复制代码

五、窗口左端移动时，如何删除？

关键点：队列里存的是 index，不是值

当 l 右移：

if maxdq[0] == l:
maxdq.popleft()
if mindq[0] == l:
mindq.popleft()

复制代码

👉 保证队首永远在窗口内

六、为什么这个方法是 O(n)？

摊还分析（面试加分点）：

每个元素：

进队一次

出队最多一次

不存在反复扫描

👉 总操作 ≤ 2n

七、用一句话记住单调队列

队列里不是当前窗口的所有元素，而是“候选最值”

先清理过期元素，再取答案（模板顺序）

推荐顺序永远是：

push 新元素

pop 过期元素

取答案

这样你不会出现：

队首已经出窗口，但你还拿它当 max 的情况

from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
maxdq = deque() # store indices, values are decreasing
res = []
for r in range(len(nums)):
# 1. maintain decreasing deque
while maxdq and nums[r] >= nums[maxdq[-1]]:
maxdq.pop()
maxdq.append(r)
# 2. remove out-of-window index
if maxdq[0] <= r - k:
maxdq.popleft()
# 3. record answer when window is ready
if r >= k - 1:
res.append(nums[maxdq[0]])
return res

复制代码

Myron2017

LC 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

from collections import deque
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
"""
【整体思路】
使用滑动窗口 + 单调队列，维护当前窗口内的最大值和最小值。
核心不变量：
- maxdq：单调递减队列，队头始终是当前窗口的「最大值索引」
- mindq：单调递增队列，队头始终是当前窗口的「最小值索引」
注意：
- 队列里存的是【索引 index】，不是值
因为：
1️⃣ 我们要判断某个元素是否已经移出窗口（index < left）
2️⃣ 通过 nums[index] 才能拿到真实值
滑动规则：
- right 每次右移，加入新元素
- 若 max - min > limit，说明窗口非法，必须不断移动 left 缩小窗口
- 只有在窗口合法时，才更新答案
"""
maxdq = deque() # 存 index，对应的 nums[index] 单调递减
mindq = deque() # 存 index，对应的 nums[index] 单调递增
left = 0
ans = 0
for right in range(len(nums)):
# ===============================
# 1. 将 nums[right] 加入 maxdq
# 保证队列从大到小（队头最大）
# ===============================
while maxdq and nums[maxdq[-1]] < nums[right]:
maxdq.pop()
maxdq.append(right)
# ===============================
# 2. 将 nums[right] 加入 mindq
# 保证队列从小到大（队头最小）
# ===============================
while mindq and nums[mindq[-1]] > nums[right]:
mindq.pop()
mindq.append(right)
# ===============================
# 3. 如果当前窗口不合法：
# max - min > limit
# 就不断移动 left 缩小窗口
# ===============================
while nums[maxdq[0]] - nums[mindq[0]] > limit:
# 如果窗口左端元素正好是最大值 / 最小值
# 需要把对应的 index 从队列中弹出
if maxdq[0] == left:
maxdq.popleft()
if mindq[0] == left:
mindq.popleft()
left += 1
# ===============================
# 4. 明确判断窗口合法后，再更新答案
# ===============================
if nums[maxdq[0]] - nums[mindq[0]] <= limit:
ans = max(ans, right - left + 1)
return ans

复制代码

Myron2017

LC 1382. Balance a Binary Search Tree

基础题，但是还是很好的练习题，不是那种故意出来刁难你的题。

就是考察你的基本功和刷题细节把握能力。

BST 的中序遍历 = 有序数组

用有序数组建平衡 BST：每次取中点

分治函数的参数 l, r 就是“你能用的数据范围”，绝不能跳出

🔑 一句“防 bug 心法”（这题的精髓）

递归参数定义了边界，
递归调用必须严格在这个边界内。

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# 用来存储 BST 中序遍历得到的「有序节点值」
vals_list = []
def inOrder(node):
"""
中序遍历（Left -> Root -> Right）
对 BST 来说，中序遍历结果一定是升序数组
"""
if not node:
return
inOrder(node.left) # 访问左子树
vals_list.append(node.val) # 当前节点值加入数组
inOrder(node.right) # 访问右子树
# Step 1: 将 BST 转换成有序数组
inOrder(root)
def buildBlancedBST(l, r):
"""
使用 vals_list[l : r+1] 这一段有序数组，
构建一棵「高度平衡 BST」
l, r 表示当前递归函数可以使用的数组边界
"""
# 递归终止条件：区间为空
if l > r:
return None
# 选择中点作为当前子树的根节点
# 这样可以保证左右子树节点数量尽量相等
mid = (l + r) // 2
# 创建当前根节点
node = TreeNode(val=vals_list[mid])
# 左子树：使用 [l, mid-1]
node.left = buildBlancedBST(l, mid - 1)
# 右子树：使用 [mid+1, r]
node.right = buildBlancedBST(mid + 1, r)
return node
# Step 2: 用整个有序数组构建平衡 BST
new_root = buildBlancedBST(0, len(vals_list) - 1)
return new_root

复制代码

Myron2017

LC 283. Move Zeroes

283. 移动零 - 核心总结
🎯 题目要求

将所有 0 移到数组末尾
保持非零元素的相对顺序
原地修改（不能创建新数组）

💡 核心思路：双指针分区
本质：通过 slow 和 fast 指针，把非零元素不断向前压缩
pythonslow = 0  # 慢指针：下一个非零元素应该放的位置

for fast in range(len(nums)):  # 快指针：遍历寻找非零元素
if nums[fast] != 0:
      if slow != fast:  # 优化：避免自我交换
         nums[slow], nums[fast] = nums[fast], nums[slow]
      slow += 1
```

## 📊 指针含义

| 指针 | 作用 |
|------|------|
| `slow` | 维护"非零区域"的边界，指向下一个非零元素的位置 |
| `fast` | 探索整个数组，寻找非零元素 |

## 🔍 数组分区（任意时刻）
```
[非零元素区 | 零元素区 | 未处理区]
↑       ↑       ↑
0       slow    fast

[0, slow)：已处理的非零元素
[slow, fast)：已处理的零
[fast, end)：未处理

⚡ 复杂度

时间：O(n) - 一次遍历
空间：O(1) - 原地修改

🔑 关键点

slow 始终指向下一个非零元素该放的位置
fast 找到非零元素就交换到 slow 位置
添加 if slow != fast 避免无用的自我交换

📝 记忆口诀

fast 探路找非零，swap 到 slow 再前进

class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
if fast != slow:
nums[fast], nums[slow] = nums[slow], nums[fast]
slow += 1

复制代码

Myron2017

LC. 109. Convert Sorted List to Binary Search Tree

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
val_list = []
node = head
while node:
val_list.append(node.val)
node = node.next
def buildBalancedBST(l, r):
if l > r: return None
mid = (l+r)//2
node = TreeNode(val = val_list[mid])
node.left = buildBalancedBST(l, mid - 1)
node.right = buildBalancedBST(mid + 1, r)
return node
root = buildBalancedBST(0, len(val_list) - 1)
return root

复制代码

Myron2017

LC 2196. Create Binary Tree From Descriptions

经典题目，我非常喜欢这个题目，充分利用了数据结构来解决问题。

通过 node_dict, children—set，val-set 来构建树，同时 track 出 root。

自然高效。

利用哈希表快速构建树，并通过集合操作找到根节点。

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
"""
从描述数组构建二叉树
核心思路：
1. 用哈希表存储所有节点（值 -> 节点对象）
2. 用集合记录所有子节点
3. 根节点 = 不在子节点集合中的节点
时间复杂度：O(n) - n 是描述数量
空间复杂度：O(n) - 存储所有节点
"""
# 存储所有节点：{节点值: TreeNode对象}
nodes = {}
# 记录所有作为子节点的值（用于找根节点）
children = set()
# 遍历所有父子关系描述
for parent_val, child_val, is_left in descriptions:
# 创建或获取父节点
if parent_val not in nodes:
nodes[parent_val] = TreeNode(parent_val)
# 创建或获取子节点
if child_val not in nodes:
nodes[child_val] = TreeNode(child_val)
# 建立父子关系
if is_left == 1: # 左孩子
nodes[parent_val].left = nodes[child_val]
else: # 右孩子 (is_left == 0)
nodes[parent_val].right = nodes[child_val]
# 记录子节点
children.add(child_val)
# 找根节点：遍历所有节点，找到不在 children 中的节点
for val in nodes:
if val not in children:
return nodes[val]
# 题目保证有效树，理论上不会执行到这里
return None

复制代码

Myron2017

LC . 26. Remove Duplicates from Sorted Array

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
"""
双指针法：slow-fast
思路：
- slow: 指向下一个不重复元素的位置
- fast: 遍历数组寻找新元素
- 当 nums[fast] != nums[slow-1] 时，说明找到新元素
时间复杂度：O(n)
空间复杂度：O(1)
"""
# 边界情况：空数组或单元素
if len(nums) <= 1:
return len(nums)
# slow 初始化为 1（第一个元素必定保留）
slow = 1
# fast 从索引 1 开始遍历
for fast in range(1, len(nums)):
# 如果当前元素与上一个不重复元素不同
if nums[fast] != nums[slow - 1]:
nums[slow] = nums[fast] # 放到 slow 位置
slow += 1 # slow 前进
return slow # slow 就是不重复元素的个数

复制代码

Myron2017

LC. 27. Remove Element

class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
"""
双指针法：slow-fast
思路：
- slow: 指向下一个保留元素的位置
- fast: 遍历数组寻找不等于 val 的元素
- 找到就放到 slow 位置，slow 前进
时间复杂度：O(n)
空间复杂度：O(1)
"""
slow = 0 # 慢指针：保留元素的边界
for fast in range(len(nums)):
# 如果当前元素不等于 val，保留它
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow # slow 就是保留元素的个数

复制代码

Myron2017

LC 80. Remove Duplicates from Sorted Array II

双指针（slow-fast）
关键观察：

每个元素最多保留 2 次
数组已排序 → 重复元素必定相邻
判断标准：当前元素是否与 slow-2 位置的元素相同

核心逻辑：
如果 nums[fast] != nums[slow-2]：
说明当前元素最多出现了 1 次，可以保留
否则：
说明已经有 2 个相同元素了，跳过

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
"""
双指针法：允许最多保留 2 个重复元素
核心思想：
- slow: 指向下一个元素应该放置的位置
- fast: 遍历数组
- 判断条件：nums[fast] 与 nums[slow-2] 比较
为什么比较 slow-2？
- slow-1: 上一个放入的元素
- slow-2: 上上个放入的元素
- 如果 nums[fast] == nums[slow-2]，说明已经有 2 个相同的了
时间复杂度：O(n)
空间复杂度：O(1)
"""
# 边界情况：长度 <= 2 的数组直接返回
if len(nums) <= 2:
return len(nums)
# slow 从索引 2 开始（前两个元素必定保留）
slow = 2
# fast 从索引 2 开始遍历
for fast in range(2, len(nums)):
# 如果当前元素与 slow-2 位置不同
# 说明当前元素最多出现了 1 次，可以保留
if nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slow

复制代码

通用解法：保留 k 个重复元素

关键点：

✅ 前 k 个元素必定保留（slow 从 k 开始）
✅ 比较 nums[fast] 和 nums[slow-k]
✅ 利用有序性：重复元素必定相邻
✅ 通用模板：可扩展到保留 k 次

class Solution:
def removeDuplicates(self, nums: List[int], k: int = 2) -> int:
"""
通用解法：最多保留 k 个重复元素
k=1: 每个元素最多 1 次（题目 26）
k=2: 每个元素最多 2 次（题目 80）
k=3: 每个元素最多 3 次
"""
if len(nums) <= k:
return len(nums)
slow = k # 前 k 个元素必定保留
for fast in range(k, len(nums)):
# 与 slow-k 位置比较
if nums[fast] != nums[slow - k]:
nums[slow] = nums[fast]
slow += 1
return slow

复制代码

刷题记录帖子

浏览过的版块