Hot100刷题记录

栈

在 Python 算法题中：

✅ 栈（Stack）直接用 list 是标准且推荐的做法
✅ 队列（Queue）必须用 collections.deque 才能保证性能

下面从底层原理和刷题实践角度为你拆解原因：

🔍 为什么栈直接用 `list`？

Python 的 list 底层是动态数组，而栈的本质是 LIFO（后进先出），只涉及末尾操作：

操作	`list` 实现	时间复杂度
入栈 `push`	`lst.append(x)`	均摊 `O(1)`
出栈 `pop`	`lst.pop()`	`O(1)`
查看栈顶	`lst[-1]`	`O(1)`

因为只操作数组尾部，不会触发元素迁移，性能极佳。且 list 是内置类型，无需 import，代码更简洁。你的写法 st = [] + st.append()/st.pop() 是 LeetCode 满分标准写法。

🚫 为什么队列不能用 `list`？

队列是 FIFO（先进先出），需要队尾入队、队首出队：

操作	`list` 实现	时间复杂度	致命问题
入队	`lst.append(x)`	`O(1)`	✅
出队	`lst.pop(0)` 或 `del lst[0]`	`O(n)` ❌	每次删除队首，后续所有元素需向前移动一位

当队列长度达到 10^4 ~ 10^5 时，list.pop(0) 会直接导致 TLE（超时）。

✅ 正确做法：队列使用 `collections.deque`

deque（双端队列）底层是分块双向链表，两端操作均为严格的 O(1)：

from collections import deque

q = deque()
q.append(1)      # 队尾入队 O(1)
q.append(2)
q.popleft()      # 队首出队 O(1) ✅
q[0]             # 查看队首 O(1)

📖 Python 官方文档明确说明： “deque 是作为快速插入和删除两端元素的数据结构而设计的。虽然 list 也支持类似操作，但针对固定长度操作进行了优化，导致 append() 和 pop() 较快，但 pop(0) 和 insert(0, v) 较慢。”

📊 算法题数据结构选型速查表

需求	推荐类型	原因
栈（LIFO）	`list`（`[]`）	末尾操作 `O(1)`，零额外开销，代码最简
队列（FIFO）	`collections.deque`	两端 `O(1)`，避免 `list.pop(0)` 的 `O(n)` 陷阱
双端队列	`collections.deque`	唯一支持两端高效插入/删除的内置结构
优先队列/堆	`heapq` 模块 + `list`	底层二叉堆，`heappush/heappop` 为 `O(log n)`
有序字典/集合	`dict` / `set`（Python 3.7+）	内置哈希表，平均 `O(1)` 查找/插入

💡 刷题实战建议

栈：闭眼用 []，配合 append() / pop() / [-1]
队列：开头加 from collections import deque，用 deque() 替代 []
别过度设计：算法题不需要线程安全（queue.Queue 会引入锁开销，反而慢）
极端情况：如果题目明确 n ≤ 100，用 list 模拟队列也能过，但养成 deque 习惯更稳妥

你的代码完全符合 Pythonic 规范，继续保持即可！遇到 BFS/滑动窗口/层序遍历时记得换成 deque 就好。需要我提供一份 deque 在经典题型（如二叉树层序遍历、滑动窗口最大值）中的标准模板吗？

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2:
            return False
        mp = {')': '(', ']': '[', '}': '{'}
        st = []
        for c in s:
            if c not in mp: # 左括号,入栈
                st.append(c)
            else:
                if not st or st.pop() != mp[c]:
                    return False
        return not st

经典的括号匹配问题，建立一个栈维持左括号。

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_element = float('inf')


    def push(self, val: int) -> None:
        self.stack.append(val)
        if val < self.min_element:
            self.min_element = val


    def pop(self) -> None:
        value = self.stack.pop()
        if value == self.min_element:
            self.min_element = float('inf')
            for val in self.stack:
                if val < self.min_element:
                    self.min_element = val


    def top(self) -> int:
        return self.stack[-1]


    def getMin(self) -> int:
        return self.min_element



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

栈的 [-1] 操作，返回栈顶元素。

灵神的解法：

class MinStack:
    def __init__(self):
        # 这里的 0 写成任意数都可以，反正用不到
        self.st = [(0, inf)]  # 栈底哨兵

    def push(self, val: int) -> None:
        self.st.append((val, min(self.st[-1][1], val)))

    def pop(self) -> None:
        self.st.pop()

    def top(self) -> int:
        return self.st[-1][0]

    def getMin(self) -> int:
        return self.st[-1][1]

神了，维持二维数组，既保留了当前元素的值，也保留了此前元素的最小值。最小前缀和，妙哉！

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n          # 初始化结果数组，默认0表示之后无更高温度
        st = []                # 单调栈，存储索引，对应温度从栈底到栈顶严格递减

        # 从右向左遍历，栈中自然保留的是“右侧的日期”
        for i in range(n - 1, -1, -1):
            t = temperatures[i]

            # 淘汰无用的候选：栈顶温度 <= 当前温度，说明栈顶不可能成为左边的答案
            while st and t >= temperatures[st[-1]]:
                st.pop()

            # 栈不为空时，栈顶就是右侧第一个温度更高的日期索引
            if st:
                ans[i] = st[-1] - i

            # 当前日期入栈，作为左边日期的候选
            st.append(i)

        return ans

这是一道经典的 单调栈（Monotonic Stack） 问题。你的代码非常优雅，使用了 倒序遍历 + 单调递减栈 的写法。下面为你拆解底层逻辑。

🎯 一句话总结

用栈维护“右侧可能成为下一个更高温度的候选日期索引”。倒序遍历时，遇到比栈顶温度高或相等的日期就弹出（因为它们被当前日期“挡住”了，对左边没用了），栈顶剩下的就是右侧第一个更高的日期。

🧩 核心逻辑：为什么这样设计？

问题本质	找每个位置右侧第一个大于它的元素
暴力法	对每个 `i` 向右遍历找 `> temperatures[i]` 的索引 → `O(n²)` 超时
单调栈优化	栈内索引对应的温度从栈底到栈顶严格递减。这样栈顶永远是离当前位置最近且温度更高的候选
倒序遍历的优势	从右往左扫，对于第 `i` 天，栈里存的天然就是 `i` 右边的日子。直接看栈顶即可，逻辑更线性

🔑 核心 `while` 循环的物理意义

while st and t >= temperatures[st[-1]]:
    st.pop()

如果当前温度 t >= 栈顶那天的温度，说明栈顶那天 不可能成为 i 左边任何一天的答案。
为什么？ 因为对于左边某天 k 来说，当前天 i 离 k 更近，且温度 >= 栈顶天。栈顶天被 i “完美覆盖”了，直接淘汰（弹出）。
循环结束后，要么栈空（右边没有更高的），要么栈顶就是 右侧第一个温度更高的日期。

📝 执行流程图解（示例：`[73, 74, 75, 71, 69, 72, 76, 73]`）

为节省篇幅，只演示关键几步：

当前索引 `i`	温度 `t`	栈变化 `st` (存索引)	计算 `ans[i]`	说明
7	73	`[7]`	`0`	栈空入栈
6	76	`[]` → `[6]`	`0`	`76 >= 73`，弹出7。栈空，右边无更高
5	72	`[6, 5]`	`6-5=1`	`72 < 76`，栈顶6是答案
4	69	`[6, 5, 4]`	`5-4=1`	`69 < 72`，栈顶5是答案
3	71	`[6, 3]`	`5-3=2`	`71 >= 69` 弹出4；`71 < 72` 停止。栈顶5是答案
...	...	...	...	继续向左推进

💡 你会发现：每个索引最多入栈1次、出栈1次，没有冗余比较。

📊 复杂度分析

维度	复杂度	说明
时间	`O(n)`	每个元素入栈1次，最多出栈1次，均摊 `O(1)`
空间	`O(n)`	`ans` 数组 `O(n)` + 栈最坏 `O(n)`（温度严格递减时）

💡 关键细节 & 面试常问

为什么用 >= 而不是 >？
相等温度不算“更暖和”，且保留相等元素对左边毫无意义（当前元素更近），所以 >= 直接弹出，保持栈内严格递减，减少冗余状态。
能正序遍历吗？
能。正序逻辑是：“当前元素作为栈顶元素的下一个更高温度”。遇到更高的就弹出栈顶并记录结果。两者时间复杂度相同，倒序写法代码更短，正序写法更符合“从左向右扫描”的直觉。面试时两种均可，倒序更不易写错边界。
栈里为什么存索引不存温度？
因为最终要返回的是 天数差值 st[-1] - i，必须知道原始位置。

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

class Solution:
    def decodeString(self, s: str) -> str:
        count_stack = []  # 存储倍数
        str_stack = []    # 存储外层已解析的字符串前缀
        cur_num = 0
        cur_str = ""

        for c in s:
            if c.isdigit():
                cur_num = cur_num * 10 + int(c)
            elif c == '[':
                # 遇到 '['，保存当前状态，进入新层级
                count_stack.append(cur_num)
                str_stack.append(cur_str)
                cur_num = 0
                cur_str = ""
            elif c == ']':
                # 遇到 ']'，弹出栈顶状态，拼接当前层结果
                repeat_times = count_stack.pop()
                last_str = str_stack.pop()
                cur_str = last_str + cur_str * repeat_times
            else:
                # 普通字母，追加到当前层字符串
                cur_str += c

        return cur_str

就是按照题目进行模拟就行。

柱形图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 首尾补 0：开头的 0 防栈空，结尾的 0 强制清空栈
        heights = [0] + heights + [0]
        st = [0]          # 单调递增栈，存索引
        max_area = 0

        for i in range(1, len(heights)):
            # 当前高度小于栈顶，说明栈顶柱子的右边界找到了
            while heights[i] < heights[st[-1]]:
                h = heights[st.pop()]      # 弹出栈顶作为矩形高度
                w = i - st[-1] - 1         # 宽度 = 右边界(i) - 左边界(新栈顶) - 1
                max_area = max(max_area, h * w)
            st.append(i)

        return max_area

🎯 核心思想：以每个柱子为“最短边”向两侧扩展

矩形的面积 = 高度 × 宽度。对于任意柱子 i，如果它作为矩形的最短边，那么它的左右边界一定是第一个比它矮的柱子。宽度 = 右边界索引 - 左边界索引 - 1 我们只需要对每个柱子，快速找到它左右两侧第一个比它矮的位置，就能算出以它为高的最大矩形，最后取全局最大值。

🧠 为什么用单调栈？

暴力找左右边界是 O(n²)。单调递增栈可以在 O(n) 时间内一次性求出所有柱子的边界：

栈内存储索引，对应高度从栈底到栈顶单调不减
当遇到比栈顶矮的柱子时，说明栈顶柱子的右边界已确定。此时弹出栈顶，它的左边界就是新栈顶（因为栈递增，新栈顶必然是左边第一个比它矮的）
每个索引入栈、出栈各一次，均摊 O(1)

📝 算法步骤（哨兵技巧版）

在原数组首尾各补一个 0（哨兵），彻底消除边界特判
初始化 st = [0]（存索引，栈底 0 是左哨兵），max_area = 0
遍历索引 i 从 1 到 len(heights)-1：
- 若 heights[i] < heights[st[-1]]，循环弹出栈顶 top
- 计算面积：h = heights[top], w = i - st[-1] - 1
- 更新 max_area = max(max_area, h * w)
- 将 i 入栈
返回 max_area

✅ Python 代码

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 首尾补 0：开头的 0 防栈空，结尾的 0 强制清空栈
        heights = [0] + heights + [0]
        st = [0]          # 单调递增栈，存索引
        max_area = 0

        for i in range(1, len(heights)):
            # 当前高度小于栈顶，说明栈顶柱子的右边界找到了
            while heights[i] < heights[st[-1]]:
                h = heights[st.pop()]      # 弹出栈顶作为矩形高度
                w = i - st[-1] - 1         # 宽度 = 右边界(i) - 左边界(新栈顶) - 1
                max_area = max(max_area, h * w)
            st.append(i)

        return max_area

💡 为什么加哨兵 `0` 这么巧妙？

不加哨兵：需额外处理 st 为空的情况（左边界不存在），且遍历结束后栈内剩余元素需单独循环计算。
加哨兵：开头的 0 保证 st 永远有底（st[-1] 不越界）；结尾的 0 会像“推土机”一样，把栈里所有比 0 高的柱子依次弹出，自动完成收尾计算。代码从 20+ 行精简到 10 行内，且零边界分支。

📊 复杂度分析

维度	复杂度	说明
时间	`O(n)`	每个索引入栈 1 次、出栈 1 次，均摊 `O(1)`
空间	`O(n)`	栈最大深度为 `n`（高度严格递增时）

🚀 面试常问 & 扩展

为什么用 < 而不是 <=？
用 < 保持栈内非严格递增。相等高度时推迟计算不影响结果，因为最后一个相等高度出栈时，宽度会自然覆盖前面所有相等柱子。
不修改原数组怎么写？
可在循环外加 while st: 处理剩余元素，或在遍历中用 heights[i] 动态判断。但哨兵法是工业级标准，面试直接写更稳妥。
高频扩展：LeetCode 85. 最大矩形（二维 01 矩阵）→ 逐行累加高度压缩成一维柱状图，直接复用本题函数即可。

堆

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

from typing import List

class Solution:
    def max_heapify(self, a: List[int], i: int, heap_size: int) -> None:
        """
        维护最大堆性质：确保以i为根的子树满足最大堆
        时间复杂度: O(log n)

        Args:
            a: 数组（用数组模拟堆）
            i: 当前需要调整的节点索引
            heap_size: 当前堆的有效大小（可能小于数组长度）
        """
        # 计算左右孩子的索引
        left = 2 * i + 1
        right = 2 * i + 2

        # 假设当前节点是最大的
        largest = i

        # 如果左孩子存在且比当前最大值大，更新largest
        if left < heap_size and a[left] > a[largest]:
            largest = left

        # 如果右孩子存在且比当前最大值大，更新largest
        if right < heap_size and a[right] > a[largest]:
            largest = right

        # 如果最大值不是当前节点，说明需要交换
        if largest != i:
            # 交换当前节点和最大值节点
            a[i], a[largest] = a[largest], a[i]
            # 递归调整被交换的子树（因为交换可能破坏了子树的堆性质）
            self.max_heapify(a, largest, heap_size)

    def build_max_heap(self, a: List[int], heap_size: int) -> None:
        """
        构建最大堆：将整个数组调整为最大堆
        时间复杂度: O(n) - 看似O(n log n)，但数学证明是O(n)

        Args:
            a: 待建堆的数组
            heap_size: 堆的大小
        """
        # 从最后一个非叶子节点开始，自底向上调整
        # 最后一个非叶子节点索引 = heap_size // 2 - 1
        # 叶子节点本身就是一个堆，无需调整
        for i in range(heap_size // 2 - 1, -1, -1):
            self.max_heapify(a, i, heap_size)

    def findKthLargest(self, nums: List[int], k: int) -> int:
        """
        找到数组中第k大的元素
        核心思路：建最大堆 + 执行k-1次提取最大值操作
        时间复杂度: O(n + k log n)，空间复杂度: O(1)

        Args:
            nums: 输入数组
            k: 找第k大（k=1表示最大值，k=2表示第二大...）

        Returns:
            第k大的元素值
        """
        heap_size = len(nums)

        # 步骤1: 构建最大堆
        # 建堆后，nums[0]就是整个数组的最大值
        self.build_max_heap(nums, heap_size)

        # 步骤2: 执行k-1次"提取堆顶"操作
        # 每次操作后，当前最大值被放到数组末尾（已排序区域）
        # 循环条件：从最后一个位置开始，执行k-1次
        for i in range(len(nums) - 1, len(nums) - k, -1):
            # 2.1 将堆顶（当前最大值）与堆末尾元素交换
            nums[0], nums[i] = nums[i], nums[0]

            # 2.2 缩小堆的有效范围（末尾元素已归位，不再参与堆调整）
            heap_size -= 1

            # 2.3 重新调整堆顶，恢复最大堆性质
            # 注意：只需要从根节点(0)开始向下调整一次
            self.max_heapify(nums, 0, heap_size)

        # 步骤3: 经过k-1次提取后，堆顶就是第k大的元素
        return nums[0]

上述代码展示了利用列表模拟堆来实现数组中的第K个最大元素。可以看到堆的数组表示,索引计算是其核心,找第K大的数字,我们也就可以建最大堆,剔除k-1次堆顶元素,此时剩余的堆顶即为答案.

不去自己实现堆,而是使用库函数，如heapq，也可以实现。

import heapq
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        """
        使用小顶堆维护k个最大元素
        堆顶始终是这k个元素中最小的，即第k大
        时间: O(n log k), 空间: O(k)
        """
        min_heap = []

        for num in nums:
            if len(min_heap) < k:
                # 堆未满，直接加入
                heapq.heappush(min_heap, num)
            elif num > min_heap[0]:
                # 当前数比堆顶大，替换堆顶
                heapq.heapreplace(min_heap, num)
            # else: 当前数太小，忽略

        # 堆顶就是第k大的元素
        return min_heap[0]

这个堆最终维护的也就是整个数组的前K个最大元素。而作为最小堆，堆顶元素最小，因此堆顶的元素就是第k大的元素。

但复杂度也并没有降到题目所要求的\(O(n)\),使用快速选择算法来进行求解。

class Solution:
    def partition(self, nums: List[int], left: int, right: int) -> int:
        """
        在子数组 [left, right] 中随机选择一个基准元素 pivot
        根据 pivot 重新排列子数组 [left, right]
        重新排列后，<= pivot 的元素都在 pivot 的左侧，>= pivot 的元素都在 pivot 的右侧
        返回 pivot 在重新排列后的 nums 中的下标
        特别地，如果子数组的所有元素都等于 pivot，我们会返回子数组的中心下标，避免退化
        """

        # 1. 在子数组 [left, right] 中随机选择一个基准元素 pivot
        i = randint(left, right)
        pivot = nums[i]
        # 把 pivot 与子数组第一个元素交换，避免 pivot 干扰后续划分，从而简化实现逻辑
        nums[i], nums[left] = nums[left], nums[i]

        # 2. 相向双指针遍历子数组 [left + 1, right]
        # 循环不变量：在循环过程中，子数组的数据分布始终如下图
        # [ pivot | <=pivot | 尚未遍历 | >=pivot ]
        #   ^                 ^     ^         ^
        #   left              i     j         right

        i, j = left + 1, right
        while True:
            while i <= j and nums[i] < pivot:
                i += 1
            # 此时 nums[i] >= pivot

            while i <= j and nums[j] > pivot:
                j -= 1
            # 此时 nums[j] <= pivot

            if i >= j:
                break

            # 维持循环不变量
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

        # 循环结束后
        # [ pivot | <=pivot | >=pivot ]
        #   ^             ^   ^     ^
        #   left          j   i     right

        # 3. 把 pivot 与 nums[j] 交换，完成划分（partition）
        # 为什么与 j 交换？
        # 如果与 i 交换，可能会出现 i = right + 1 的情况，已经下标越界了，无法交换
        # 另一个原因是如果 nums[i] > pivot，交换会导致一个大于 pivot 的数出现在子数组最左边，不是有效划分
        # 与 j 交换，即使 j = left，交换也不会出错
        nums[left], nums[j] = nums[j], nums[left]

        # 交换后
        # [ <=pivot | pivot | >=pivot ]
        #               ^
        #               j

        # 返回 pivot 的下标
        return j

    def findKthLargest(self, nums: list[int], k: int) -> int:
        n = len(nums)
        target_index = n - k  # 第 k 大元素在升序数组中的下标是 n - k
        left, right = 0, n - 1  # 闭区间
        while True:
            i = self.partition(nums, left, right)
            if i == target_index:
                # 找到第 k 大元素
                return nums[i]
            if i > target_index:
                # 第 k 大元素在 [left, i - 1] 中
                right = i - 1
            else:
                # 第 k 大元素在 [i + 1, right] 中
                left = i + 1

也就是快速排序的思想，在快排的过程中每次都会确定一个元素的位置，我们将其加以应用，也就变成了快速选择算法。

即：

快速排序思想，基准值划分左右。
如果k比左侧大，则可将左侧舍弃，同时k也需要随着规模进行变化。

前 k 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

from collections import Counter
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 第一步：统计频次
        cnt = Counter(nums)                          # 效果：O(N) 遍历一次，生成 {元素: 出现次数} 的哈希表
        max_cnt = max(cnt.values())                  # 效果：O(U) 找出最高频次（U=不同元素个数），决定桶的数量

        # 第二步：桶排序分组（索引 = 频次，值 = 该频次的元素列表）
        buckets = [[] for _ in range(max_cnt + 1)]   # 效果：创建 max_cnt+1 个空桶，索引 i 存放频次为 i 的所有元素
        for x, c in cnt.items():                     # 效果：遍历哈希表，取出 (元素x, 频次c)
            buckets[c].append(x)                     # 效果：O(1) 将元素放入对应频次桶中，完成按频次分组

        # 第三步：逆序收集结果
        ans = []                                     # 效果：初始化结果列表
        for bucket in reversed(buckets):             # 效果：从最高频桶开始倒序遍历（频次从高到低）
            ans += bucket                            # 效果：将当前桶内元素批量拼接到 ans
            if len(ans) == k:                        # 效果：判断是否已凑齐 k 个元素
                return ans                           # 效果：提前返回，避免遍历低频空桶，保证最优时间复杂度

桶排序的思想，将元素按照频次进行分组，然后逆序收集结果。利用二维列表实现桶的模拟。

使用堆，注意要使用小顶堆，这样才能快速比较频次并进行替换。

import heapq
from collections import Counter
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 1️⃣ 统计每个元素的频次 O(N)
        cnt = Counter(nums)

        # 2️⃣ 维护一个大小为 k 的小顶堆，存储 (频次, 元素)
        min_heap = []

        for num, freq in cnt.items():
            if len(min_heap) < k:
                # 堆未满，直接入堆
                heapq.heappush(min_heap, (freq, num))
            elif freq > min_heap[0][0]:
                # 当前频次 > 堆顶频次（守门员）
                # 替换堆顶，并自动调整堆结构 O(log k)
                heapq.heapreplace(min_heap, (freq, num))

        # 3️⃣ 提取堆中所有元素（只取数字，忽略频次）
        return [num for freq, num in min_heap]

Q1：为什么不用大顶堆？

✅ 答：大顶堆需要把所有 U 个不同元素都入堆（\(O(U log U)\)），再弹出 k 次。而小顶堆只维护 k 个元素，每次比较/替换都是 \(O(log k)\)。当 k << U 时，小顶堆效率呈指数级优势。

数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。

void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

class MedianFinder:

    def __init__(self):
        self.left = [] # 最大堆
        self.right = [] # 最小堆


    def addNum(self, num: int) -> None:
        if len(self.left) == len(self.right):
            heappush_max(self.left, heappushpop(self.right, num))
        else:
            heappush(self.right, heappushpop_max(self.left, num))


    def findMedian(self) -> float:
        if len(self.left) > len(self.right):
            return self.left[0]
        return (self.left[0] + self.right[0]) / 2



# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

维护左右两个部分，左侧为最大堆，堆顶为左侧元素的最大值，右侧为最小堆，堆顶为右侧元素的最小值。始终满足左右两侧堆的元素个数之差不超过 1。

添加元素时，如果左侧元素个数等于右侧元素个数，则始终先将元素添加到右侧，再将右侧最小值添加到左侧，并更新左侧堆顶元素；如果左侧元素个数大于右侧元素个数，则先将元素添加到左侧，再将左侧最大值添加到右侧，并更新右侧堆顶元素。由此实现了写法上的统一。

贪心

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        min_price = prices[0]
        for i in range(1, len(prices)):
            ans = max(ans, prices[i] - min_price)
            if prices[i] < min_price:
                min_price = prices[i]
        return ans

低买高卖，维持一个全局的最大利润，着眼于当前天之前价格最低的那一天买入，则此时可获得当前天卖出的最大利润，比较即可。

跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 维护一个可以跳到最远多远的变量
        mx = 0
        for i, jump in enumerate(nums):
            if i > mx: # 无法到达i,没有继续更新下去的必要了
                return False
            mx = max(mx, i + jump) # 从 i 最右可以跳到 i + jump
            if mx >= len(nums) - 1:
                return True
        return True

贪心，从第一个位置开始，遍历数组，维护一个可以跳到最远多远的变量，如果当前位置 i > mx，则无法到达 i，返回 False。

跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n 返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

class Solution:
    def jump(self, nums: List[int]) -> int:
        dp = [10005] * len(nums)
        dp[0] = 0
        for i in range(len(nums)):
            for j in range(1, nums[i] + 1):
                if i + j < len(nums):
                    dp[i + j] = min(dp[i] + 1, dp[i + j])
        return dp[-1]

我本能的是想到使用动态数组，记录每个位置的最小步数，然后从后往前遍历，更新到达每个位置的最小步数。

灵神的贪心的思路：

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = 0
        cur_right = 0  # 已建造的桥的右端点
        next_right = 0  # 下一座桥的右端点的最大值
        for i in range(len(nums) - 1):
            # 遍历的过程中，记录下一座桥的最远点
            next_right = max(next_right, i + nums[i])
            if i == cur_right:  # 无路可走，必须建桥
                cur_right = next_right  # 建桥后，最远可以到达 next_right
                ans += 1
        return ans

实在走到边界时才需要建桥，同时我们应该去建目前能够跳到的最远点这座桥，才能使得所建的桥尽可能宽，也才能尽可能少的建桥。

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 记录每个字母最后出现的下标
        last = {c: i for i, c in enumerate(s)}
        ans = []
        start = -1
        end = 0
        for i, c in enumerate(s):
            # 更新当前区间需要覆盖的右端点的最大值
            end = max(end, last[c])
            # 刚好完全覆盖,代表当前区间合并完毕
            if end == i:
                ans.append(end - start)
                start = i
        return ans

由于题目要求划分出尽量多的片段，而我们又无法将上述区间的任何区间划分开，所以合并出的区间长度即为答案。

由于需要划分尽可能多的片段，所以需要记录每个字母最后出现的下标，并记录当前区间需要覆盖的右端点最大值，当当前区间的右端点等于当前下标时，说明当前区间已经完全覆盖，可以合并。

动态规划

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution:
    def climbStairs(self, n: int) -> int:
        result = [0] * (n + 1)
        result[0] = result[1] = 1
        for i in range(2, n + 1):
            result[i] = result[i-1] + result[i-2]
        return result[n]

经典的动态规划问题，状态转移方程为 f(n) = f(n-1) + f(n-2)。

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = [[1]]
        for i in range(1, numRows):
            row = []
            row.append(1)
            for j in range(1, i):
                row.append(result[-1][j-1] + result[-1][j])
            row.append(1)
            result.append(row)

        return result

这是一个经典的动态规划问题，状态转移方程为 f(i, j) = f(i-1, j-1) + f(i-1, j)。

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[n-1]

这是一个典型的动态规划问题，状态转移方程为 f(i) = max(f(i-1), f(i-2) + nums[i])。其中 f(i) 表示偷窃到第 i 个房屋时的最高金额。

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin < 0:
                    continue
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount] if dp[amount] != (amount + 1) else -1

这是一个典型的动态规划问题，状态转移方程为 f(i) = min(f(i), f(i - coin) + 1)。其中 f(i) 表示凑成金额 i 的最少硬币个数。

完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution:
    def numSquares(self, n: int) -> int:
        sqrts = []
        for j in range(1, n + 1):
            sqrts.append(j * j)
        # print (sqrts)
        dp = [n + 1] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            for num in sqrts:
                if i - num < 0:
                    break
                dp[i] = min(dp[i], dp[i - num] + 1)

        return dp[n]

我基本就是上面一题一摸一样的思路写上去。

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        result = 1
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(i - 1, -1, -1):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[j] + 1, dp[i])
            result = max(result, dp[i])
        return result

我的写法如上，其实也就是遍历数组，并记录每个位置的递增子序列的长度，最后返回最长的递增子序列的长度。

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位整数。

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        f_max = [0] * n
        f_min = [0] * n
        f_max[0] = f_min[0] = nums[0]
        for i in range(1, n):
            x = nums[i]
            f_max[i] = max(f_max[i - 1] * x, f_min[i - 1] * x, x)
            f_min[i] = min(f_max[i - 1] * x, f_min[i - 1] * x, x)
        return max(f_max)

这是一个典型的动态规划问题，状态转移方程为 f(i) = max(f(i-1) * nums[i], f(i-1) * nums[i], nums[i])。其中 f(i) 表示以第 i 个数字结尾的乘积最大的子数组。

由于数组中可能存在负数，负数乘以负数会变成正数，所以需要记录最小值，才能保证乘积最大。

分割等和数组

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:  # 和为奇数，不可能平分
            return False

        target = total // 2
        # dp[j] = 能否凑出和为 j
        dp = [False] * (target + 1)
        dp[0] = True  # 和为 0 永远可以（不选任何数）

        for num in nums:  # 遍历每个数字（物品）
            # ⚠️ 关键：倒序遍历容量，避免同一数字被重复使用
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]  # 选或不选

        return dp[target]

问题等价于能否找到一个子集使得和为 target // 2。

外层为每一个数字，由此能够保证所有物品只会被使用一次。同时内层采用倒序遍历，避免重复使用同一个数字，导致前置结果的更新对后续运算造成错误。

递归写法

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:

        @cache
        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return j == 0
            if j < nums[i]:
                return dfs(i - 1, j) # 只能不选当前物品
            return dfs(i - 1, j - nums[i]) or dfs(i - 1, j) # 选或者不选

        total = sum(nums)
        if total % 2 != 0:  # 和为奇数，不可能平分
            return False

        target = total // 2
        return dfs(len(nums) - 1, target)

递归写法，使用缓存，避免重复计算。动态规划本质上也就是解决重复子问题而设计的，这里其实就相当于普通的使用mem备忘录进行缓存动规。

自底向上还是自顶向下的区别而已，重点还是要理解状态转移方程。

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict)) # 获取最大子串的长度,用于限制下面j的循环次数
        words = set(wordDict) # 用于快速判断 s[j:i] 是否是某个子词

        @cache
        def dfs(i: int) -> bool:
            # 定义状态为dfs(i),表示能否把前缀s[:i]划分成若干段,使得每段都在wordDict中
            if i == 0: # 成功拆分
                return True
            # 枚举不同长度的子串s[j:i],看是否在集合中
            for j in range(i - 1, max(i - max_len - 1, -1), -1):
                # 在集合中就接着往前判断
                if s[j:i] in words and dfs(j):
                    return True
            return False

        return dfs(len(s))

递归写法，使用缓存，避免重复计算。

状态转移方程为 f(i) = f(j) and s[j:i] in words。

递推写法

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict))  # 用于限制下面 j 的循环次数
        words = set(wordDict)  # 便于快速判断 s[j:i] in words

        n = len(s)
        f = [True] + [False] * n
        for i in range(1, n + 1):
            for j in range(i - 1, max(i - max_len - 1, -1), -1):
                if f[j] and s[j:i] in words:
                    f[i] = True
                    break
        return f[n]

最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        st = [-1] # 虚拟红线,哨兵
        ans = 0
        for i, ch in enumerate(s):
            if ch == '(':
                st.append(i) # 压栈并记录下标
            else:
                if len(st) > 1: # ch为),且栈顶元素为(
                    st.pop()
                    ans = max(ans, i - st[-1]) # 右端点为i时,左端点最小为 st[-1] + 1,注意不是之前的栈顶,因为在此之前还有可能有能匹配的,此时需要融合
                else: # 栈中只有一个数,即目前的)无法被匹配,成为新的红线起点
                    st[0] = i
        return ans

感觉还得再想想，尤其是最大长度的计算方式，上一个最远左端点的计算。

多维动态规划

不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # for i in dp[0]:
        #     i = 1
        for i in range(n):
            dp[0][i] = 1
        for i in range(m):
            dp[i][0] = 1
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m-1][n-1]

状态转移方程为 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

这是 Python 初学者极易踩的经典坑。核心原因一句话：

for i in dp[0]: 遍历的是列表元素的值，i = 1 只是改了局部变量，根本没有修改原列表。

下面用内存模型+对比+优雅写法帮你彻底理清：

🔍 为什么 `for i in dp[0]: i = 1` 无效？

dp[0] = [0, 0, 0, 0]  # 假设 n=4

for i in dp[0]:
    i = 1  # ❌ 这里发生了什么？

🧠 Python 执行过程拆解

dp[0] 是一个包含 4 个整数 0 的列表。
for i in dp[0]: 每次循环，i 会绑定到当前元素的值（即 0）。
i = 1 只是让局部变量 i 指向了新的整数对象 1。这相当于换了个标签，但原列表里的 0 纹丝不动。
整数是不可变对象，循环变量不是“引用指针”，赋值操作无法反向修改容器。

🖥️ 终端验证

arr = [0, 0, 0]
for x in arr:
    x = 99
print(arr)  # 输出: [0, 0, 0] ← 根本没变！

✅ 为什么 `for i in range(n): dp[0][i] = 1` 有效？

for i in range(n):
    dp[0][i] = 1  # ✅ 通过索引直接定位到列表的内存位置，执行原地修改

range(n) 生成的是索引 0, 1, 2...
dp[0][i] 是直接访问列表第 i 个槽位，= 执行的是赋值突变，列表内容被真实改写。

🚀 更 Pythonic 的写法（推荐）

方案1：直接替换整行（最贴近你原逻辑）

dp[0] = [1] * n  # 用新列表覆盖 dp[0] 的引用，O(1) 完成

方案2：初始化时直接搞定（最简洁，推荐⭐）

本题的 DP 特性：第一行和第一列的所有格子都只有 1 条路径。所以根本不需要分两步初始化，直接全填 1 即可：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 第一行和第一列天然都是 1，直接初始化全 1 矩阵
        dp = [[1] * n for _ in range(m)]

        # 从 (1,1) 开始动态规划
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m-1][n-1]

💡 注意：一定要用 [[1] * n for _ in range(m)]，绝不能用 [[1] * n] * m（后者会导致所有行共享同一列表，改一处全乱）。

📊 修改列表的 3 种正确姿势

场景	错误写法	正确写法	原理
遍历改值	`for x in lst: x = 1`	`for i in range(len(lst)): lst[i] = 1`	需通过索引定位修改
整体替换	`lst = [1]*len(lst)` (在函数内可能无效)	`lst[:] = [1]*len(lst)`	`[:]` 表示原地替换内容
批量赋值	`lst[0] = 1; lst[1] = 1...`	`lst = [1] * n` 或切片赋值	Python 列表支持整块替换

🎯 一句话总结

🔹 for 变量 in 列表: 变量只是值的“副本”，改它不影响原列表
🔹 想修改列表元素，必须用索引：列表[索引] = 新值
🔹 本题最优解：dp = [[1]*n for _ in range(m)]，省掉冗余初始化代码

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        for i in range(1, m):
            grid[i][0] = grid[i-1][0] + grid[i][0]
        for i in range(1, n):
            grid[0][i] = grid[0][i-1] + grid[0][i]
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
        return grid[m-1][n-1]

很明显的动态规划思路，从左上角开始，每次向右或向下移动，并计算当前位置的值。

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

中心扩展法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        ans_left = ans_right = 0 # 维护一个左闭右开区间

        # 奇回文串
        for i in range(n):
            l = r = i
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # 循环结束时,s[l+1]到s[r-1]是回文串
            if r - l - 1 > ans_right - ans_left:
                ans_left, ans_right = l + 1, r

        # 偶回文串
        for i in range(n):
            l, r = i, i + 1
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 1 > ans_right - ans_left:
                ans_left, ans_right = l + 1, r

        return s[ans_left: ans_right]

这种方法我感觉偏向暴力解法，但有效。

动态规划

🎯 一句话核心

“回文就是‘剥洋葱’：两头字符相等，且去掉两头后，中间剩下的也是回文。” DP 做的就是：把每个子串是不是回文的结果记在表格里，短子串的结果用来推导长子串。

📦 三步拆解（保姆级）

1️⃣ 状态定义：dp[i][j] 是什么？

想象一个 n×n 的表格，行和列都是字符串索引：

dp[i][j] = 子串 s[i...j] 是不是回文？
          是 → True
          否 → False

例如 s = "aba"：

dp[0][2] 表示 "aba" 是不是回文 → True
dp[0][1] 表示 "ab" 是不是回文 → False

2️⃣ 状态转移：怎么推导？

判断 s[i...j] 是不是回文，分两步：

if s[i] != s[j]:
    dp[i][j] = False  # 两头不一样，直接判死刑
else:
    # 两头一样，关键看“去掉两头后，中间是不是回文”
    if j - i < 2:     # 中间没字符（长度1或2），直接是回文
        dp[i][j] = True
    else:
        dp[i][j] = dp[i+1][j-1]  # 依赖“内侧”子串的结果

3️⃣ 遍历顺序（最容易错！）

因为 dp[i][j] 依赖 dp[i+1][j-1]（左下角的值），所以必须：

👉 i 从下往上倒着走，j 从左往右正着走
这样才能保证算 dp[i][j] 时，它需要的 dp[i+1][j-1] 已经算好了。

🖼️ 图解推演（s = "babad"）

索引:  0    1    2    3    4
字符:  b    a    b    a    d

表格填法（i 倒序, j 正序）：
i=4 (d): dp[4][4]=T
i=3 (a): dp[3][3]=T, dp[3][4]=F (a≠d)
i=2 (b): dp[2][2]=T, dp[2][3]=F, dp[2][4]=F
i=1 (a): dp[1][1]=T, dp[1][2]=F, dp[1][3]=T (aba), dp[1][4]=F
i=0 (b): dp[0][0]=T, dp[0][1]=F, dp[0][2]=T (bab), dp[0][3]=F, dp[0][4]=F

过程中记录最长：
"aba" 长度3 → 记录
"bab" 长度3 → 记录（并列）
最终返回其中一个即可。

💻 完整代码（可直接提交）

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s  # 长度0或1，自己就是最长回文

        # dp[i][j] 表示 s[i...j] 是否为回文
        dp = [[False] * n for _ in range(n)]

        max_len = 1  # 记录最长回文长度
        start = 0    # 记录最长回文的起始索引

        # ⚠️ 关键顺序：i 从后往前，j 从 i 往后
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j - i < 2:
                        dp[i][j] = True  # 长度1或2，两头相等即为回文
                    else:
                        dp[i][j] = dp[i + 1][j - 1]  # 依赖内侧子串

                # 如果是回文，且比当前记录的最长还长，就更新
                if dp[i][j] and (j - i + 1) > max_len:
                    max_len = j - i + 1
                    start = i

        return s[start : start + max_len]

⚠️ 为什么 i 必须倒着走？（灵魂拷问）

依赖关系：dp[i][j]  ←  dp[i+1][j-1]
                ↑              ↓
              当前位置        左下角（行号+1，列号-1）

如果 i 正着走（0 → n-1）：算到 dp[0][3] 时需要 dp[1][2]，但此时 i=1 还没开始算！数据是空的 False，结果全错。

如果 i 倒着走（n-1 → 0）：算到 dp[0][3] 时，i=1 的行早就填完了，dp[1][2] 已经是正确值 ✅

💡 记忆口诀：dp[i][j] 看左下，所以 i 要从下往上填！

📊 复杂度分析

维度	分析
时间复杂度	`O(n²)`。两层嵌套循环，共填 `n(n+1)/2` 个格子，每个格子 `O(1)` 计算
空间复杂度	`O(n²)`。`dp` 表格占 `n×n` 个布尔值
实际性能	LeetCode 可 AC，但面试可补充：空间可优化到 `O(n)` 或用“中心扩展法”更省内存

💡 面试实战建议

如果面试官问：“能优化空间吗？”
✅ 答：可以！因为 dp[i][j] 只依赖上一行（i+1），可用一维数组滚动更新，空间降至 O(n)。但代码会变绕，一般写出二维即可。
如果问：“有没有更快的方法？”
✅ 答：有。中心扩展法 O(n²) 时间 O(1) 空间，常数更小；进阶可用 Manacher 算法 O(n)，但实现复杂。工程中中心扩展最常用。
避坑提醒：
- 别忘了 j - i < 2 的边界处理，否则 dp[i+1][j-1] 会越界或逻辑错误。
- 记录答案要在 if dp[i][j]: 里面，且比较长度要带 +1。

🎯 一句话总结

🔹 dp[i][j] = s[i]==s[j] 且 (长度≤2 或 dp[i+1][j-1])
🔹 i 从后往前，j 从 i 往后，保证“先算短的，再推长的”
🔹 遇到 True 就比长度，记录起点和最大长度，最后切片返回

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)

        @cache
        def dfs(i: int, j: int) -> int:
            if i < 0 or j < 0:
                return 0
            if text1[i] == text2[j]:
                return dfs(i - 1, j - 1) + 1
            return max(dfs(i - 1, j), dfs(i, j - 1))

        return dfs(m - 1, n - 1)

状态转移方程dfs(i, j)表示到下标(i, j)的子序列的最长公共子序列长度。

编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        # dp[i][j] 表示 A 的前 i 个字符转化为 B 的前 j 个字符所需要的最小操作数
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for i in range(n + 1):
            dp[0][i] = i
        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]
                else:
                    # 三种操作选一种
                    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)

        return dp[m][n]

状态dp[i][j]表示将word1[0:i]转换成word2[0:j]所使用的最少操作数。

如何理解dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)

dp[i][j] = dp[i-1][j] + 1：删除word1[i]后匹配，也就是在word1前i-1个字符匹配word2的前j个字符基础上加一。
dp[i][j] = dp[i][j-1] + 1：插入word2[j]后匹配，也就是在word1的前i个字符匹配word2的前j-1个字符基础上加一。
dp[i][j] = dp[i-1][j-1] + 1：替换word1[i]后匹配，也就是在word1前i-1个字符匹配word2的前j-1个字符基础上加一。

技巧

只出现一次的数字

异或运算

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = nums[0]
        for num in nums[1:]:
            result = result^num
        return result

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]

如何设计一个时间复杂度为 \(O(n)\) ，空间复杂度为 \(O(1)\) 的算法呢？

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        result = nums[0]
        count = 1
        for num in nums[1:]:
            if num == result:
                count += 1
            else:
                count -= 1
                if count <= 0:
                    result = num
                    count = 1

        return result

计算 nums 的绝对众数。绝对众数的出现次数，比其余所有元素的出现次数加起来还多。保证 nums 一定存在绝对众数。

下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n <= 1:
            return

        # 1. 从右向左找第一个升序对 (nums[i] < nums[i+1])
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        # 2. 如果找到了这样的 i，说明不是完全降序
        if i >= 0:
            # 从右向左找第一个大于 nums[i] 的数
            j = n - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            # 交换
            nums[i], nums[j] = nums[j], nums[i]

        # 3. 反转 i+1 到末尾的部分
        # 无论是否找到 i，这一步都要做：
        # 如果找到了 i，反转是为了让后缀变最小 (升序)
        # 如果没找到 i (i=-1)，反转整个数组变成最小 (升序)
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

正确的算法思路 (标准解法)

要找到下一个排列，我们需要尽可能小地增大这个数。标准算法分为三步，时间复杂度为 \(O(N)\)：

查找分界点 (Pivot)： 从右向左遍历，找到第一个满足 nums[i] < nums[i+1] 的索引 i。
- 这意味着 i 右边的部分是降序的（已经是该部分能组成的最大排列）。
- i 就是我们需要增大的那个位置。
- 如果找不到这样的 i（整个数组是降序），说明已经是最大排列，直接反转整个数组。
查找交换点 (Successor)： 如果找到了 i，再次从右向左遍历，找到第一个满足 nums[j] > nums[i] 的索引 j。
- 因为 i 右边是降序，从右往左找到的第一个比 nums[i] 大的数，就是右边部分中大于 nums[i] 的最小数。
交换并反转：
- 交换 nums[i] 和 nums[j]。
- 将 i+1 到末尾的部分反转（变为升序）。因为交换后这部分依然是降序，反转后变成最小的升序排列，从而保证整体增量最小。

代码执行流程示例

以 nums = [1, 3, 2] 为例：

找 i：
- 比较 3 和 2 (nums[1] vs nums[2])：3 >= 2，继续。
- 比较 1 和 3 (nums[0] vs nums[1])：1 < 3，找到！i = 0。
找 j：
- 从右往左找第一个大于 nums[0] (即 1) 的数。
- nums[2] 是 2，2 > 1，找到！j = 2。
交换：
- 交换 nums[0] 和 nums[2]。数组变为 [2, 3, 1]。
反转后缀：
- 反转 i+1 (索引 1) 到末尾。即反转 [3, 1] 变为 [1, 3]。
- 最终结果：[2, 1, 3]。 (正确)

复杂度分析

时间复杂度： \(O(N)\)。最多遍历数组两次（找 i 和找 j），反转操作也是 \(O(N)\)。
空间复杂度： \(O(1)\)。原地修改，只用了常数个变量。

使用这个逻辑即可通过 LeetCode 的 "Next Permutation" 测试用例。

寻找重复数

def findDuplicate(nums):
    # 快慢指针法
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

这是这道题最巧妙的地方！让我详细解释为什么是 nums[slow] 而不是 slow + 1。

核心概念：数组模拟链表

普通链表 vs 数组链表

普通链表	数组模拟链表
`node = node.next`	`i = nums[i]`
每个节点有 `next` 指针	数组的值就是下一个索引

为什么 `nums[i]` 是"下一步"？

题目条件的巧妙之处

题目说：数字都在 [1, n] 范围内

这意味着：

数组的值可以作为数组的索引（因为索引也是 0 到 n）
从任意位置出发，nums[i] 永远是一个有效的位置

根据鸽巢原理：

有 n+1 个位置
但只有 n 个可能的"下一步"目标
有限节点 + 每个节点必有后继 = 必然成环

图示理解

数组：nums = [1, 3, 4, 2, 2]
索引： 0   1   2   3   4
       ↓   ↓   ↓   ↓   ↓
值：   1   3   4   2   2

链表关系：
位置 0 的值是 1 → 下一步跳到位置 1
位置 1 的值是 3 → 下一步跳到位置 3
位置 3 的值是 2 → 下一步跳到位置 2
位置 2 的值是 4 → 下一步跳到位置 4
位置 4 的值是 2 → 下一步跳到位置 2 (环！)

可视化：
0 → 1 → 3 → 2 → 4
            ↑   ↓
            ←←←←
            环入口是位置 2，值是 2（重复数）

代码对比

普通链表

# 链表节点
class Node:
    def __init__(self, val):
        self.val = val
        self.next = next_node

# 走一步
slow = slow.next

数组模拟链表

# 数组的"next 指针"就是值本身
# 走一步
slow = nums[slow]      # 当前位置 slow，下一步是 nums[slow]

# 走两步
fast = nums[nums[fast]]  # 先走一步 nums[fast]，再走一步 nums[nums[fast]]

完整执行过程示例

nums = [1, 3, 4, 2, 2]

初始：slow = 0, fast = 0

第一轮：
  slow = nums[0] = 1
  fast = nums[nums[0]] = nums[1] = 3

第二轮：
  slow = nums[1] = 3
  fast = nums[nums[3]] = nums[2] = 4

第三轮：
  slow = nums[3] = 2
  fast = nums[nums[4]] = nums[2] = 4

第四轮：
  slow = nums[2] = 4
  fast = nums[nums[4]] = nums[2] = 4

相遇！slow == fast == 4

为什么不是 `slow + 1`？

❌ 错误理解：slow = slow + 1
   这是顺序遍历数组，不是遍历"链表"

✅ 正确理解：slow = nums[slow]
   这是按照数组值指向的"指针"走

对比

如果用 slow + 1：
0 → 1 → 2 → 3 → 4 (只是顺序遍历，找不到环)

如果用 nums[slow]：
0 → 1 → 3 → 2 → 4 → 2 → 4 → ... (形成环，能找到重复数)

关键总结

概念	含义
`i`	当前所在的位置（索引）
`nums[i]`	从位置 `i` 出发，下一步要去的位置
`nums[slow]`	慢指针走一步
`nums[nums[fast]]`	快指针走两步

本质： 我们把数组的值当成了"指针"，构建了一个隐式的链表结构。重复的数会导致多个位置指向同一个位置，从而形成环。🎯

Hot100刷题记录

栈

🔍 为什么栈直接用 list？

🚫 为什么队列不能用 list？

✅ 正确做法：队列使用 collections.deque

📊 算法题数据结构选型速查表

💡 刷题实战建议

有效的括号

最小栈

每日温度

🎯 一句话总结

🧩 核心逻辑：为什么这样设计？

🔑 核心 while 循环的物理意义

📝 执行流程图解（示例：[73, 74, 75, 71, 69, 72, 76, 73]）

📊 复杂度分析

💡 关键细节 & 面试常问

字符串解码

柱形图中最大的矩形

🎯 核心思想：以每个柱子为“最短边”向两侧扩展

🧠 为什么用单调栈？

📝 算法步骤（哨兵技巧版）

✅ Python 代码

💡 为什么加哨兵 0 这么巧妙？

📊 复杂度分析

🚀 面试常问 & 扩展

堆

数组中的第K个最大元素

前 k 个高频元素

数据流的中位数

贪心

买卖股票的最佳时机

跳跃游戏

跳跃游戏 II

划分字母区间

动态规划

爬楼梯

杨辉三角

打家劫舍

零钱兑换

完全平方数

最长递增子序列

乘积最大子数组

分割等和数组

递归写法

单词拆分

递推写法

最长有效括号

多维动态规划

不同路径

🔍 为什么 for i in dp[0]: i = 1 无效？

🧠 Python 执行过程拆解

🖥️ 终端验证

✅ 为什么 for i in range(n): dp[0][i] = 1 有效？

🚀 更 Pythonic 的写法（推荐）

方案1：直接替换整行（最贴近你原逻辑）

方案2：初始化时直接搞定（最简洁，推荐⭐）

📊 修改列表的 3 种正确姿势

🎯 一句话总结

最小路径和

最长回文子串

中心扩展法

动态规划

最长公共子序列

编辑距离

技巧

只出现一次的数字

多数元素

下一个排列

正确的算法思路 (标准解法)

代码执行流程示例

复杂度分析

寻找重复数

核心概念：数组模拟链表

为什么 nums[i] 是"下一步"？

图示理解

代码对比

完整执行过程示例

为什么不是 slow + 1？

关键总结

🔍 为什么栈直接用 `list`？

🚫 为什么队列不能用 `list`？

✅ 正确做法：队列使用 `collections.deque`

🔑 核心 `while` 循环的物理意义

📝 执行流程图解（示例：`[73, 74, 75, 71, 69, 72, 76, 73]`）

💡 为什么加哨兵 `0` 这么巧妙？

🔍 为什么 `for i in dp[0]: i = 1` 无效？

✅ 为什么 `for i in range(n): dp[0][i] = 1` 有效？

为什么 `nums[i]` 是"下一步"？

为什么不是 `slow + 1`？