LeetCode HOT100 困难题
首发 2026/05/10
阅读 0
评论 0
更新 2026/05/10
LeetCode HOT100 困难题详细学习版
目录
- LC 4 寻找两个正序数组的中位数
- LC 10 正则表达式匹配
- LC 23 合并 K 个升序链表
- LC 32 最长有效括号
- LC 42 接雨水
- LC 72 编辑距离
- LC 76 最小覆盖子串
- LC 84 柱状图中最大的矩形
- LC 85 最大矩形
- LC 124 二叉树中的最大路径和
- LC 239 滑动窗口最大值
- LC 297 二叉树的序列化与反序列化
- LC 301 删除无效的括号
- LC 312 戳气球
1. LC 4 寻找两个正序数组的中位数
难度：困难
标签：数组、二分
原题简述
两个升序数组，要求 O(log(m+n)) 找整体中位数。
知识点介绍
中位数可转化为找第 k 小元素；每次比较两个数组第 k/2 个候选，排除较小那一段。
标准思路
递归/循环找第 k 小，处理中位数奇偶。
最优标准解
python
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def kth(a_start, b_start, k):
if a_start == len(nums1):
return nums2[b_start + k - 1]
if b_start == len(nums2):
return nums1[a_start + k - 1]
if k == 1:
return min(nums1[a_start], nums2[b_start])
i = min(a_start + k // 2 - 1, len(nums1) - 1)
j = min(b_start + k // 2 - 1, len(nums2) - 1)
if nums1[i] <= nums2[j]:
return kth(i + 1, b_start, k - (i - a_start + 1))
return kth(a_start, j + 1, k - (j - b_start + 1))
total = len(nums1) + len(nums2)
if total % 2:
return kth(0, 0, total // 2 + 1)
return (kth(0, 0, total // 2) + kth(0, 0, total // 2 + 1)) / 2复杂度
时间 O(log(m+n))，空间 O(log(m+n)) 递归栈。
易错点
k 是第 k 小，注意 1-based；某数组耗尽要直接取另一个。
多解补充
多解 1：合并后取中位数
取舍说明： 简单但 O(m+n)，不满足最优。
python
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
arr=sorted(nums1+nums2)
n=len(arr)
return arr[n//2] if n%2 else (arr[n//2-1]+arr[n//2])/2快速复习
中位数：转第 k 小，每次排除一段。
2. LC 10 正则表达式匹配
难度：困难
标签：动态规划、字符串
原题简述
实现支持 '.' 和 '*' 的正则匹配，要求匹配整个字符串。
知识点介绍
dp[i][j] 表示 s 前 i 个字符能否被 p 前 j 个字符匹配。
标准思路
普通字符或 '.' 看前一格；'*' 可以匹配零次或多次前一个字符。
最优标准解
python
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m,n=len(s),len(p)
dp=[[False]*(n+1) for _ in range(m+1)] # dp[i][j] 表示 s 前 i 个字符能否匹配 p 前 j 个字符
dp[0][0]=True # dp[i][j] 表示 s 前 i 个字符能否匹配 p 前 j 个字符
for j in range(2,n+1):
if p[j-1]=='*':
dp[0][j]=dp[0][j-2] # dp[i][j] 表示 s 前 i 个字符能否匹配 p 前 j 个字符
for i in range(1,m+1):
for j in range(1,n+1):
if p[j-1] in {s[i-1],'.'}:
dp[i][j]=dp[i-1][j-1] # dp[i][j] 表示 s 前 i 个字符能否匹配 p 前 j 个字符
elif p[j-1]=='*':
dp[i][j]=dp[i][j-2] # dp[i][j] 表示 s 前 i 个字符能否匹配 p 前 j 个字符
if p[j-2] in {s[i-1],'.'}:
dp[i][j]=dp[i][j] or dp[i-1][j] # dp[i][j] 表示 s 前 i 个字符能否匹配 p 前 j 个字符
return dp[m][n]复杂度
时间 O(mn)，空间 O(mn)。
易错点
'*' 作用于前一个字符；匹配整个字符串不是子串。
多解补充
多解 1：递归记忆化
取舍说明： 同样清晰，但要缓存避免指数爆炸。
python
from functools import lru_cache
class Solution:
def isMatch(self, s: str, p: str) -> bool:
@lru_cache(None)
def dfs(i,j):
if j==len(p):
return i==len(s)
first=i<len(s) and p[j] in {s[i],'.'}
if j+1<len(p) and p[j+1]=='*':
return dfs(i,j+2) or (first and dfs(i+1,j))
return first and dfs(i+1,j+1)
return dfs(0,0)快速复习
正则匹配：二维 DP，星号零次/多次。
3. LC 23 合并 K 个升序链表
难度：困难
标签：链表、堆、分治
原题简述
合并 k 个升序链表成一个升序链表。
知识点介绍
堆可以每次取当前最小节点；分治可以两两合并。
标准思路
把每个链表头放入小根堆，弹出最小节点后把它的 next 放回堆。
最优标准解
python
from typing import List, Optional
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap=[]
for i,node in enumerate(lists):
if node:
heapq.heappush(heap,(node.val,i,node))
dummy=cur=ListNode()
while heap:
_,i,node=heapq.heappop(heap)
cur.next=node
cur=cur.next
if node.next:
heapq.heappush(heap,(node.next.val,i,node.next))
return dummy.next # 返回虚拟头节点后面的真实链表头复杂度
时间 O(N log k)，空间 O(k)。
易错点
堆中加 i 避免节点值相等时无法比较 ListNode。
多解补充
多解 1：分治两两合并
取舍说明： 同样优秀，时间 O(N log k)，不依赖堆。
python
from typing import List, Optional
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def merge(a,b):
dummy=cur=ListNode()
while a and b:
if a.val<=b.val:
cur.next=a
a=a.next
else:
cur.next=b
b=b.next
cur=cur.next
cur.next=a if a else b
return dummy.next # 返回虚拟头节点后面的真实链表头
if not lists:
return None # 没有可返回的节点或结果
while len(lists)>1:
merged=[]
for i in range(0,len(lists),2):
merged.append(merge(lists[i], lists[i+1] if i+1<len(lists) else None)) # 加入当前路径、节点或中间结果
lists=merged
return lists[0]快速复习
合并 K 链表：小根堆取最小。
4. LC 32 最长有效括号
难度：困难
标签：栈、动态规划
原题简述
返回最长有效括号子串长度。
知识点介绍
栈保存还没匹配的位置，栈底保存最后一个无效位置。
标准思路
遇到 '(' 入栈；遇到 ')' 弹栈，若栈空记录无效位置，否则更新长度。
最优标准解
python
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack=[-1] # 栈保存还没结算的下标或状态
ans=0
for i,ch in enumerate(s):
if ch=='(':
stack.append(i) # 加入当前路径、节点或中间结果
else:
stack.pop() # 遇到右括号，尝试匹配一个左括号
if not stack:
stack.append(i) # 加入当前路径、节点或中间结果
else:
ans=max(ans,i-stack[-1]) # 栈保存还没结算的下标或状态
return ans # 返回最终答案复杂度
时间 O(n)，空间 O(n)。
易错点
栈底 -1 是边界；栈空时要放当前无效右括号位置。
多解补充
多解 1：DP
取舍说明： 同样优秀，但状态转移更难。
python
class Solution:
def longestValidParentheses(self, s: str) -> int:
dp=[0]*len(s)
ans=0
for i in range(1,len(s)):
if s[i]==')':
if s[i-1]=='(':
dp[i]=(dp[i-2] if i>=2 else 0)+2
else:
j=i-dp[i-1]-1
if j>=0 and s[j]=='(':
dp[i]=dp[i-1]+2+(dp[j-1] if j>=1 else 0)
ans=max(ans,dp[i])
return ans # 返回最终答案快速复习
最长有效括号：栈存边界。
5. LC 42 接雨水
难度：困难
标签：双指针、单调栈
原题简述
给柱子高度，求能接多少雨水。
知识点介绍
每个位置水量由左右最大高度的较小值决定。
标准思路
双指针维护 left_max/right_max，哪边较低就结算哪边。
最优标准解
python
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
left,right=0,len(height)-1
left_max=right_max=0 # 记录左侧目前遇到的最高柱子
ans=0
while left<right:
if height[left]<height[right]:
left_max=max(left_max,height[left]) # 记录左侧目前遇到的最高柱子
ans+=left_max-height[left] # 记录左侧目前遇到的最高柱子
left+=1
else:
right_max=max(right_max,height[right]) # 记录右侧目前遇到的最高柱子
ans+=right_max-height[right] # 记录右侧目前遇到的最高柱子
right-=1
return ans # 返回最终答案复杂度
时间 O(n)，空间 O(1)。
易错点
结算较矮一侧；水量不能为负，因为先更新 max。
多解补充
多解 1：前后缀最大
取舍说明： 更直观但空间 O(n)。
python
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
n=len(height)
left=[0]*n
right=[0]*n
for i in range(1,n): left[i]=max(left[i-1],height[i-1])
for i in range(n-2,-1,-1): right[i]=max(right[i+1],height[i+1])
return sum(max(0,min(left[i],right[i])-height[i]) for i in range(n))快速复习
接雨水：双指针维护左右最大。
6. LC 72 编辑距离
难度：困难
标签：动态规划、字符串
原题简述
给两个单词，求把 word1 转成 word2 的最少操作数，操作为插入、删除、替换。
知识点介绍
dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。
标准思路
字符相同看 dp[i-1][j-1]，不同则从插入/删除/替换三种操作取最小 +1。
最优标准解
python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m,n=len(word1),len(word2)
dp=[[0]*(n+1) for _ in range(m+1)] # 创建 DP 表，保存子问题答案
for i in range(m+1): dp[i][0]=i # 创建 DP 表，保存子问题答案
for j in range(n+1): dp[0][j]=j # 创建 DP 表，保存子问题答案
for i in range(1,m+1):
for j in range(1,n+1):
if word1[i-1]==word2[j-1]:
dp[i][j]=dp[i-1][j-1] # 创建 DP 表，保存子问题答案
else:
dp[i][j]=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 # 创建 DP 表，保存子问题答案
return dp[m][n]复杂度
时间 O(mn)，空间 O(mn)。
易错点
初始化空串转换；下标 i 对应 word1[i-1]。
多解补充
多解 1：空间压缩
取舍说明： 同样转移，空间降为 O(n)。
python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n=len(word2)
dp=list(range(n+1)) # 创建 DP 表，保存子问题答案
for i,c1 in enumerate(word1,1):
prev=dp[0] # 创建 DP 表，保存子问题答案
dp[0]=i # 创建 DP 表，保存子问题答案
for j,c2 in enumerate(word2,1):
tmp=dp[j] # 创建 DP 表，保存子问题答案
dp[j]=prev if c1==c2 else min(dp[j],dp[j-1],prev)+1 # 创建 DP 表，保存子问题答案
prev=tmp
return dp[n]快速复习
编辑距离：插删改三选一。
7. LC 76 最小覆盖子串
难度：困难
标签：滑动窗口、哈希表
原题简述
在 s 中找包含 t 所有字符的最短子串。
知识点介绍
窗口计数满足 need 后，尝试收缩左边界。
标准思路
right 扩大窗口，formed 表示满足需求的字符种类数；满足后不断移动 left 缩短。
最优标准解
python
from collections import Counter, defaultdict
class Solution:
def minWindow(self, s: str, t: str) -> str:
need=Counter(t) # 统计 t 中每个字符需要的次数
window=defaultdict(int) # 统计当前窗口中相关字符出现次数
required=len(need) # 统计 t 中每个字符需要的次数
formed=0
left=0
best=(float('inf'),0,0)
for right,ch in enumerate(s):
window[ch]+=1 # 统计当前窗口中相关字符出现次数
if ch in need and window[ch]==need[ch]: # 统计 t 中每个字符需要的次数
formed+=1
while formed==required:
if right-left+1<best[0]:
best=(right-left+1,left,right)
c=s[left]
window[c]-=1 # 统计当前窗口中相关字符出现次数
if c in need and window[c]<need[c]: # 统计 t 中每个字符需要的次数
formed-=1
left+=1
return '' if best[0]==float('inf') else s[best[1]:best[2]+1]复杂度
时间 O(n)，空间 O(字符集)。
易错点
窗口满足后要尽量收缩；t 有重复字符。
多解补充
多解 1：暴力检查窗口
取舍说明： 能做但 O(n²) 以上，不推荐。
python
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
need=Counter(t) # 统计 t 中每个字符需要的次数
ans=''
for i in range(len(s)):
cnt=Counter()
for j in range(i,len(s)):
cnt[s[j]]+=1
if all(cnt[c]>=need[c] for c in need): # 统计 t 中每个字符需要的次数
if not ans or j-i+1<len(ans):
ans=s[i:j+1]
break
return ans # 返回最终答案快速复习
最小覆盖：滑动窗口满足后收缩。
8. LC 84 柱状图中最大的矩形
难度：困难
标签：单调栈
原题简述
给柱状图高度，求最大矩形面积。
知识点介绍
单调递增栈中柱子等待右侧第一个更矮柱子来结算面积。
标准思路
在末尾加 0 触发所有柱子出栈，弹出高度时用左右边界算宽度。
最优标准解
python
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack=[] # 栈保存还没结算的下标或状态
ans=0
heights.append(0) # 加入当前路径、节点或中间结果
for i,h in enumerate(heights):
while stack and heights[stack[-1]]>h: # 单调递增栈保存还没确定右边界的柱子下标
height=heights[stack.pop()] # 栈保存还没结算的下标或状态
left=stack[-1] if stack else -1 # 栈保存还没结算的下标或状态
ans=max(ans,height*(i-left-1))
stack.append(i) # 加入当前路径、节点或中间结果
heights.pop()
return ans # 返回最终答案复杂度
时间 O(n)，空间 O(n)。
易错点
宽度是 i-left-1；末尾哨兵 0 很关键。
多解补充
多解 1：暴力扩展
取舍说明： 能做但 O(n²)。
python
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
ans=0
for i in range(len(heights)):
mn=float('inf')
for j in range(i,len(heights)):
mn=min(mn,heights[j])
ans=max(ans,mn*(j-i+1))
return ans # 返回最终答案快速复习
柱状图：单调递增栈结算面积。
9. LC 85 最大矩形
难度：困难
标签：动态规划、单调栈
原题简述
在 0/1 矩阵中找只含 1 的最大矩形面积。
知识点介绍
把每一行看成柱状图底边，连续 1 的高度就是柱高。
标准思路
逐行更新 heights，对每行调用柱状图最大矩形。
最优标准解
python
from typing import List
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
n=len(matrix[0])
heights=[0]*n
ans=0
def largest(h):
stack=[] # 单调递增栈保存还没确定右边界的柱子下标
best=0
h.append(0) # 加入当前路径、节点或中间结果
for i,x in enumerate(h):
while stack and h[stack[-1]]>x: # 单调递增栈保存还没确定右边界的柱子下标
height=h[stack.pop()] # 单调递增栈保存还没确定右边界的柱子下标
left=stack[-1] if stack else -1 # 单调递增栈保存还没确定右边界的柱子下标
best=max(best,height*(i-left-1))
stack.append(i) # 加入当前路径、节点或中间结果
h.pop()
return best
for row in matrix:
for j,ch in enumerate(row):
heights[j]=heights[j]+1 if ch=='1' else 0
ans=max(ans, largest(heights))
return ans # 返回最终答案复杂度
时间 O(mn)，空间 O(n)。
易错点
每行 heights 遇 0 要清零。
多解补充
多解 1：宽度 DP
取舍说明： 也可做，但实现更不如单调栈统一。
python
from typing import List
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m,n=len(matrix),len(matrix[0])
width=[[0]*n for _ in range(m)] # 宽度由当前位置和弹出后新的栈顶共同决定
ans=0
for i in range(m):
for j in range(n):
if matrix[i][j]=='1':
width[i][j]=(width[i][j-1] if j else 0)+1 # 宽度由当前位置和弹出后新的栈顶共同决定
mn=width[i][j] # 宽度由当前位置和弹出后新的栈顶共同决定
for k in range(i,-1,-1):
mn=min(mn,width[k][j]) # 宽度由当前位置和弹出后新的栈顶共同决定
ans=max(ans,mn*(i-k+1))
return ans # 返回最终答案快速复习
最大矩形：每行转柱状图。
10. LC 124 二叉树中的最大路径和
难度：困难
标签：树、DFS
原题简述
路径可以从任意节点到任意节点，求最大路径和。
知识点介绍
对父节点而言，一个节点只能贡献一条向下路径；但答案可在当前节点处合并左右贡献。
标准思路
DFS 返回向父节点贡献的最大单边和，同时更新经过当前节点的全局最大路径。
最优标准解
python
from typing import Optional
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
ans=float('-inf') # 最大路径和可能为负数，所以初始为负无穷
def gain(node):
nonlocal ans
if not node: # 空节点是递归边界
return 0
left=max(gain(node.left),0)
right=max(gain(node.right),0)
ans=max(ans,node.val+left+right)
return node.val+max(left,right)
gain(root)
return ans # 返回最终答案复杂度
时间 O(n)，空间 O(h)。
易错点
返回给父节点只能选一边；全负数时 ans 初始化负无穷。
多解补充
多解 1：枚举每个节点暴力求贡献
取舍说明： 可想但会重复计算，最坏 O(n²)。
python
from typing import Optional
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
ans=float('-inf') # 最大路径和可能为负数，所以初始为负无穷
def one_side(node):
if not node: # 空节点是递归边界
return 0
return node.val+max(0,one_side(node.left),one_side(node.right))
def walk(node):
nonlocal ans
if not node: # 空节点是递归边界
return # 结束当前递归分支
ans=max(ans,node.val+max(0,one_side(node.left))+max(0,one_side(node.right)))
walk(node.left)
walk(node.right)
walk(root)
return ans # 返回最终答案快速复习
最大路径和：更新左右合并，返回单边贡献。
11. LC 239 滑动窗口最大值
难度：困难
标签：单调队列、堆
原题简述
给定窗口大小 k，返回每个窗口最大值。
知识点介绍
单调队列保存可能成为最大值的下标，队头始终是当前窗口最大值。
标准思路
新元素进来时弹出所有比它小的尾部元素；队头过期就弹出。
最优标准解
python
from typing import List
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q=deque() # 双端队列维护当前窗口的候选最大值下标
ans=[]
for i,x in enumerate(nums):
while q and nums[q[-1]]<=x:
q.pop()
q.append(i) # 加入当前路径、节点或中间结果
if q[0] <= i-k:
q.popleft()
if i >= k-1:
ans.append(nums[q[0]]) # 队头下标对应当前窗口最大值
return ans # 返回最终答案复杂度
时间 O(n)，空间 O(k)。
易错点
队列存下标；过期判断是 q[0] <= i-k。
多解补充
多解 1：堆
取舍说明： 也能做，O(n log n)，需要处理过期下标。
python
from typing import List
import heapq
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
heap=[]
ans=[]
for i,x in enumerate(nums):
heapq.heappush(heap,(-x,i))
while heap[0][1] <= i-k:
heapq.heappop(heap)
if i>=k-1:
ans.append(-heap[0][0])
return ans # 返回最终答案快速复习
滑动窗口最大：单调递减队列。
12. LC 297 二叉树的序列化与反序列化
难度：困难
标签：树、BFS、DFS、设计
原题简述
将二叉树编码成字符串，再从字符串恢复树。
知识点介绍
必须记录空节点，否则结构无法唯一恢复。
标准思路
用层序 BFS，空节点记为 #，反序列化时按顺序给每个节点接左右孩子。
最优标准解
python
from collections import deque
class Codec:
def serialize(self, root):
if not root:
return ''
q=deque([root]) # 队列用于按层遍历二叉树
vals=[]
while q:
node=q.popleft()
if node:
vals.append(str(node.val)) # 加入当前路径、节点或中间结果
q.append(node.left) # 加入当前路径、节点或中间结果
q.append(node.right) # 加入当前路径、节点或中间结果
else:
vals.append('#') # 加入当前路径、节点或中间结果
return ','.join(vals)
def deserialize(self, data):
if not data:
return None # 没有可返回的节点或结果
vals=data.split(',')
root=TreeNode(int(vals[0]))
q=deque([root]) # 队列用于按层遍历二叉树
i=1
while q:
node=q.popleft()
if vals[i] != '#':
node.left=TreeNode(int(vals[i]))
q.append(node.left) # 加入当前路径、节点或中间结果
i+=1
if vals[i] != '#':
node.right=TreeNode(int(vals[i]))
q.append(node.right) # 加入当前路径、节点或中间结果
i+=1
return root # 返回处理后的根节点复杂度
时间 O(n)，空间 O(n)。
易错点
必须保留空节点标记；反序列化索引要按左右孩子推进。
多解补充
多解 1：前序 DFS
取舍说明： 同样优秀，递归结构更紧凑。
python
class Codec:
def serialize(self, root):
if not root:
return '#'
return str(root.val)+','+self.serialize(root.left)+','+self.serialize(root.right)
def deserialize(self, data):
vals=iter(data.split(','))
def build():
v=next(vals) # 按序列化顺序取出下一个标记
if v=='#':
return None # 没有可返回的节点或结果
node=TreeNode(int(v))
node.left=build()
node.right=build()
return node # 返回当前构造出的节点
return build()快速复习
序列化树：记录空节点。
13. LC 301 删除无效的括号
难度：困难
标签：BFS、回溯
原题简述
删除最少数量无效括号，返回所有可能有效结果。
知识点介绍
BFS 按删除次数分层，第一次找到有效字符串时就是最少删除。
标准思路
从当前层生成删除一个括号后的字符串，找到有效后不再向更深层扩展。
最优标准解
python
from typing import List
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
def valid(x):
bal=0
for ch in x:
if ch=='(':
bal+=1
elif ch==')':
bal-=1
if bal<0:
return False # 当前情况不符合题意
return bal==0
level={s}
while True:
ans=[x for x in level if valid(x)]
if ans:
return ans # 返回最终答案
nxt=set()
for x in level:
for i,ch in enumerate(x):
if ch in '()':
nxt.add(x[:i]+x[i+1:])
level=nxt复杂度
时间指数级，空间指数级；但 BFS 保证最少删除。
易错点
只删除括号；用 set 去重。
多解补充
多解 1：回溯预计算删几个
取舍说明： 更高效但实现更复杂。
python
from typing import List
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
lrem=rrem=0
for ch in s:
if ch=='(':
lrem+=1
elif ch==')':
if lrem:
lrem-=1
else:
rrem+=1
ans=set()
def dfs(i,lcnt,rcnt,lrem,rrem,path):
if i==len(s):
if lrem==rrem==0 and lcnt==rcnt:
ans.add(''.join(path))
return # 结束当前递归分支
ch=s[i]
if ch=='(' and lrem>0:
dfs(i+1,lcnt,rcnt,lrem-1,rrem,path)
if ch==')' and rrem>0:
dfs(i+1,lcnt,rcnt,lrem,rrem-1,path)
path.append(ch) # 加入当前路径、节点或中间结果
if ch not in '()':
dfs(i+1,lcnt,rcnt,lrem,rrem,path)
elif ch=='(':
dfs(i+1,lcnt+1,rcnt,lrem,rrem,path)
elif rcnt<lcnt:
dfs(i+1,lcnt,rcnt+1,lrem,rrem,path)
path.pop() # 回溯撤销当前字符，尝试删除或其他选择
dfs(0,0,0,lrem,rrem,[])
return list(ans)快速复习
删无效括号：BFS 分层，首次有效即最少。
14. LC 312 戳气球
难度：困难
标签：区间 DP
原题简述
戳破气球获得 nums[left]*nums[i]*nums[right]，求最大金币。
知识点介绍
区间 DP 常反过来想：最后戳区间中的哪个气球。
标准思路
加上两端虚拟 1，dp[l][r] 表示开区间 (l,r) 内气球全部戳完的最大金币。
最优标准解
python
from typing import List
class Solution:
def maxCoins(self, nums: List[int]) -> int:
arr=[1]+nums+[1]
n=len(arr)
dp=[[0]*n for _ in range(n)] # 创建 DP 表，保存子问题答案
for length in range(2,n):
for l in range(0,n-length):
r=l+length
for k in range(l+1,r): # 枚举 k 作为当前区间最后一个被戳的气球
dp[l][r]=max(dp[l][r], dp[l][k]+dp[k][r]+arr[l]*arr[k]*arr[r]) # 创建 DP 表，保存子问题答案
return dp[0][n-1]复杂度
时间 O(n³)，空间 O(n²)。
易错点
dp 是开区间；想最后戳哪个气球。
多解补充
多解 1：记忆化搜索
取舍说明： 同样的区间 DP，写法更递归化。
python
from typing import List
from functools import lru_cache
class Solution:
def maxCoins(self, nums: List[int]) -> int:
arr=[1]+nums+[1]
@lru_cache(None)
def f(l,r):
if r-l<=1:
return 0
return max(f(l,k)+f(k,r)+arr[l]*arr[k]*arr[r] for k in range(l+1,r)) # 在不同选择中取收益最大的方案
return f(0,len(arr)-1)快速复习
戳气球：区间 DP，枚举最后戳。