困难题清单

一句话说明

困难题通常不是引入全新语法，而是在状态设计、数据结构组合和复杂度优化上同时卡你。

进入困难题前最好先稳住的专题

• 动态规划
• 树形递归
• 单调栈 / 单调队列
• 回溯剪枝
• 图最短路 / 拓扑 / 网络流

常见困难题来源

主题	代表题型	难点
DP	编辑距离、戳气球	状态设计
树与图	最大路径和、序列化	多状态合并
栈队列	接雨水、最大矩形	结构维护
搜索	解数独、N 皇后	剪枝强度

一个代表性 Go 模板：接雨水双指针

func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    answer := 0
 
    for left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                answer += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                answer += rightMax - height[right]
            }
            right--
        }
    }
 
    return answer
}

一个代表性 Go 模板：记忆化 DFS

func longestIncreasingPath(matrix [][]int) int {
    rows, cols := len(matrix), len(matrix[0])
    memo := make([][]int, rows)
    for i := range memo {
        memo[i] = make([]int, cols)
    }
    dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
 
    var dfs func(r, c int) int
    dfs = func(r, c int) int {
        if memo[r][c] != 0 {
            return memo[r][c]
        }
        best := 1
        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
                continue
            }
            if matrix[nr][nc] > matrix[r][c] {
                best = max(best, 1+dfs(nr, nc))
            }
        }
        memo[r][c] = best
        return best
    }
 
    answer := 0
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            answer = max(answer, dfs(i, j))
        }
    }
    return answer
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

刷题建议

• 困难题不要追求刷得快，要追求能复盘清楚
• 一题不会时，优先补专题，不要只背答案
• 能把“为什么这个优化成立”讲清楚，才算真的掌握

---

返回：LeetCode题解