size = 2 * k + 1

旧窗口：[2, 4, 6]
新窗口：   [4, 6, 8]

左边的 2 离开窗口
右边的 8 进入窗口

window -= left_item
window += right_item

size = k
window = sum(nums[:size])
answer = 处理第一扇窗口

for right in range(size, len(nums)):
    left = right - size

    window -= nums[left]       # 左边元素离开
    window += nums[right]      # 右边元素进入

    更新答案

right = 新进入窗口的元素下标
left = right - size = 离开窗口的元素下标

窗口状态：当前窗口中的元音数量
答案：所有窗口中最大的元音数量

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set("aeiou")

        vowel_count = 0
        for i in range(k):
            if s[i] in vowels:
                vowel_count += 1

        answer = vowel_count

        for right in range(k, len(s)):
            left = right - k

            if s[left] in vowels:
                vowel_count -= 1
            if s[right] in vowels:
                vowel_count += 1

            answer = max(answer, vowel_count)

        return answer

窗口平均值最大，等价于窗口和最大。

window_sum = 当前窗口的和
max_sum = 出现过的最大窗口和

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = sum(nums[:k])
        max_sum = window_sum

        for right in range(k, len(nums)):
            left = right - k

            window_sum -= nums[left]
            window_sum += nums[right]

            max_sum = max(max_sum, window_sum)

        return max_sum / k

window_sum / k >= threshold

window_sum >= k * threshold

643：记录最大的窗口和
1343：统计合格窗口的数量

class Solution:
    def numOfSubarrays(
        self, arr: List[int], k: int, threshold: int
    ) -> int:
        target = k * threshold
        window_sum = sum(arr[:k])

        answer = 0
        if window_sum >= target:
            answer += 1

        for right in range(k, len(arr)):
            left = right - k

            window_sum -= arr[left]
            window_sum += arr[right]

            if window_sum >= target:
                answer += 1

        return answer

nums[i - k : i + k + 1]

size = 2 * k + 1

i - k >= 0
i + k < len(nums)

k <= i < len(nums) - k

answer = [-1] * len(nums)

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        size = 2 * k + 1
        answer = [-1] * n

        if size > n:
            return answer

        window_sum = sum(nums[:size])
        answer[k] = window_sum // size

        for center in range(k + 1, n - k):
            left_out = center - k - 1
            right_in = center + k

            window_sum -= nums[left_out]
            window_sum += nums[right_in]

            answer[center] = window_sum // size

        return answer

left_out = center - k - 1  # 旧窗口最左边的元素
right_in = center + k      # 新窗口最右边的元素

减去左边离开的元素，加上右边进入的元素。

窗口中有几个 W，就需要涂色几次。

在所有长度为 k 的窗口中，寻找 W 数量最少的窗口。

窗口状态：当前窗口中的白块数量
答案：所有窗口中最少的白块数量

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        white_count = blocks[:k].count('W')
        answer = white_count

        for right in range(k, len(blocks)):
            left = right - k

            if blocks[left] == 'W':
                white_count -= 1
            if blocks[right] == 'W':
                white_count += 1

            answer = min(answer, white_count)

        return answer

1456：统计元音数量，求最大值
2379：统计白块数量，求最小值

window_sum = 当前窗口的元素和
freq = 当前窗口中每个数字的出现次数

len(freq)

len(freq) >= m

[1, 1, 2]

freq[left_num] -= 1

if freq[left_num] == 0:
    del freq[left_num]

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        freq = {}
        window_sum = 0

        # 建立第一扇窗口
        for i in range(k):
            num = nums[i]
            window_sum += num
            freq[num] = freq.get(num, 0) + 1

        answer = 0

        if len(freq) >= m:
            answer = window_sum

        # 窗口向右滑动
        for right in range(k, len(nums)):
            left = right - k
            left_num = nums[left]
            right_num = nums[right]

            # 左边数字离开窗口
            window_sum -= left_num
            freq[left_num] -= 1

            if freq[left_num] == 0:
                del freq[left_num]

            # 右边数字进入窗口
            window_sum += right_num
            freq[right_num] = freq.get(right_num, 0) + 1

            if len(freq) >= m:
                answer = max(answer, window_sum)

        return answer

窗口和 + 窗口内每个数字的出现次数

size = n - k

从两端拿走 k 张牌
等价于
在中间留下长度为 n-k 的连续子数组

拿走的点数 = 所有牌的总和 - 剩下的点数

寻找长度为 n-k、元素和最小的连续子数组。

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        total = sum(cardPoints)

        # 中间留下的窗口长度
        size = n - k

        # 所有牌都要拿走
        if size == 0:
            return total

        window_sum = sum(cardPoints[:size])
        min_sum = window_sum

        for right in range(size, n):
            left = right - size

            window_sum -= cardPoints[left]
            window_sum += cardPoints[right]

            min_sum = min(min_sum, window_sum)

        return total - min_sum

cardPoints = [1, 2, 3, 4, 5, 6, 1]
k = 3

size = 7 - 3 = 4

[1, 2, 3, 4] → 10
[2, 3, 4, 5] → 14
[3, 4, 5, 6] → 18
[4, 5, 6, 1] → 16

22 - 10 = 12

两端拿走 k 张的最大和
→ 中间留下 n-k 张的最小和
→ 长度为 n-k 的定长滑动窗口

base = 0

for i in range(len(customers)):
    if grumpy[i] == 0:
        base += customers[i]

原本就满意的顾客 base + 最多能够挽回的顾客 max_extra

class Solution:
    def maxSatisfied(
        self,
        customers: List[int],
        grumpy: List[int],
        minutes: int
    ) -> int:
        n = len(customers)

        # 原本就满意的顾客
        base = 0

        for i in range(n):
            if grumpy[i] == 0:
                base += customers[i]

        # 第一扇窗口能够额外挽回的顾客
        extra = 0

        for i in range(minutes):
            if grumpy[i] == 1:
                extra += customers[i]

        max_extra = extra

        # 窗口向右滑动
        for right in range(minutes, n):
            left = right - minutes

            if grumpy[left] == 1:
                extra -= customers[left]

            if grumpy[right] == 1:
                extra += customers[right]

            max_extra = max(max_extra, extra)

        return base + max_extra

customers = [1, 0, 1, 2, 1, 1, 7, 5]
grumpy    = [0, 1, 0, 1, 0, 1, 0, 1]
minutes = 3

base = 1 + 1 + 1 + 7 = 10

第 0～2 分钟：0
第 1～3 分钟：2
第 2～4 分钟：2
第 3～5 分钟：3
第 4～6 分钟：1
第 5～7 分钟：6

1 + 5 = 6

10 + 6 = 16

if grumpy[i] == 1:
    extra += customers[i]

固定的基础收益 + 滑动窗口带来的最大额外收益

固定窗口长度
→ 先计算第一扇窗口
→ 减去左边离开的元素
→ 加上右边进入的元素
→ 按题目要求记录答案

对每一个元素，寻找它左边或右边第一个比它大（或比它小）的元素。

新元素满足栈顶等待的条件
→ 栈顶找到了答案
→ 弹出栈顶并记录答案
→ 继续检查新的栈顶

1. 栈里是谁在等待答案？
2. 它在等待什么条件？
3. 当前元素能不能解决栈顶？
4. 如果能，答案应该记录在哪里？

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
answer       = [ 1,  1,  4,  2,  1,  1,  0,  0]

对每一天
右边
第一个更高温度

for i in range(n):
    for j in range(i + 1, n):
        if temperatures[j] > temperatures[i]:
            answer[i] = j - i
            break

stack = []  # 尚未找到更高温度的日期下标

等待天数 = 当前日期下标 - 旧日期下标

previous_index = stack[-1]
previous_temperature = temperatures[previous_index]
distance = current_index - previous_index

temperatures[stack[0]] >= temperatures[stack[1]] >= ... >= temperatures[stack[-1]]

while stack and temperatures[i] > temperatures[stack[-1]]:
    previous_index = stack.pop()
    answer[previous_index] = i - previous_index

stack.append(i)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = []

        for current_index in range(n):
            while (
                stack
                and temperatures[current_index] > temperatures[stack[-1]]
            ):
                previous_index = stack.pop()
                answer[previous_index] = current_index - previous_index

            stack.append(current_index)

        return answer

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []

        for i, current_temperature in enumerate(temperatures):
            while stack and current_temperature > temperatures[stack[-1]]:
                previous_index = stack.pop()
                answer[previous_index] = i - previous_index

            stack.append(i)

        return answer

temperatures = [75, 71, 69, 72]

72 > 69，解决温度 69 对应的日期
72 > 71，继续解决温度 71 对应的日期
72 < 75，停止弹栈

temperatures = [73, 73, 74]

answer = [2, 1, 0]

current_temperature > temperatures[stack[-1]]

while stack != []:
    if current_temperature > temperatures[stack[-1]]:
        # 弹栈并记录答案
    else:
        break

while stack and current_temperature > temperatures[stack[-1]]:
    previous_index = stack.pop()
    answer[previous_index] = i - previous_index

answer = [0] * len(nums)
stack = []  # 保存还没有找到答案的下标

for i in range(len(nums)):
    while stack and nums[i] > nums[stack[-1]]:
        previous_index = stack.pop()
        answer[previous_index] = i - previous_index

    stack.append(i)

弹栈条件：找更大还是找更小，严格还是允许相等
记录内容：记录元素值、下标，还是下标之间的距离

栈中保存还没等到更高温度的日期；
新温度到来时，连续解决所有比它低的栈顶日期；
弹出谁，就把距离写到谁的答案中；
最后再把当前日期入栈，等待未来处理。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

        3
       / \
      9  20
        /  \
       15   7

递归向下：把问题交给更小的子树
递归返回：把子树的结果交回上一层

遇到空节点：什么都不做，直接返回
遇到非空节点：先记录自己，再遍历左子树，最后遍历右子树

class Solution:
    def preorderTraversal(self, root):
        answer = []

        def dfs(node):
            if node is None:
                return

            answer.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return answer

当前子树的最大深度 = max(左子树深度, 右子树深度) + 1

class Solution:
    def maxDepth(self, root):
        def depth(node):
            if node is None:
                return 0

            left_depth = depth(node.left)
            right_depth = depth(node.right)
            return max(left_depth, right_depth) + 1

        return depth(root)

depth(9)  = max(0, 0) + 1 = 1
depth(15) = max(0, 0) + 1 = 1
depth(7)  = max(0, 0) + 1 = 1
depth(20) = max(1, 1) + 1 = 2
depth(3)  = max(1, 2) + 1 = 3

        3
       / \
      5   1
     / \
    6   2
       / \
      7   4

左边非空，右边非空 → 两个目标分居两侧，返回当前节点
只有左边非空       → 把左边的结果继续向上传
只有右边非空       → 把右边的结果继续向上传
两边都为空         → 返回 None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        def dfs(node):
            if node is None or node is p or node is q:
                return node

            left = dfs(node.left)
            right = dfs(node.right)

            if left is not None and right is not None:
                return node
            if left is not None:
                return left
            return right

        return dfs(root)

节点 6：命中 p，返回节点 6
节点 7：没有目标，返回 None
节点 4：命中 q，返回节点 4
节点 2：左边 None，右边 4，返回节点 4
节点 5：左边 6，右边 4，两边都非空，返回节点 5
节点 1：没有目标，返回 None
节点 3：左边 5，右边 None，继续返回节点 5

from collections import deque


class Solution:
    def levelOrder(self, root):
        if root is None:
            return []

        queue = deque([root])
        answer = []

        while queue:
            level_size = len(queue)
            level = []

            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)

                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)

            answer.append(level)

        return answer

左子树的所有节点值 < 当前节点值 < 右子树的所有节点值

        5
       / \
      1   7
         / \
        4   8

进入左子树：保留原下界，把上界缩小为当前值
进入右子树：把下界提高为当前值，保留原上界

class Solution:
    def isValidBST(self, root):
        def dfs(node, lower, upper):
            if node is None:
                return True

            if not (lower < node.val < upper):
                return False

            return (
                dfs(node.left, lower, node.val)
                and dfs(node.right, node.val, upper)
            )

        return dfs(root, float('-inf'), float('inf'))

节点 5：允许范围 (-∞, +∞)，合法
节点 7：在 5 的右侧，允许范围 (5, +∞)，合法
节点 4：在 7 的左侧，但仍在 5 的右子树中
        允许范围 (5, 7)，4 不在其中，返回 False

前序：根 | 左子树 | 右子树  → 确定根是谁
中序：左子树 | 根 | 右子树  → 确定左右子树分别有哪些节点

前序：[3, 9, 20, 15, 7]
中序：[9, 3, 15, 20, 7]

第一步：前序第一个值是 3，所以根是 3。
第二步：在中序里找到 3。
        左子树中序：[9]，共 1 个节点
        右子树中序：[15, 20, 7]，共 3 个节点
第三步：前序去掉根后，接下来的 1 个节点属于左子树。
        左子树前序：[9]
        右子树前序：[20, 15, 7]

build(pre_left, in_left, in_right)

作用：构造中序区间 [in_left, in_right) 对应的子树
pre_left：这棵子树的根在前序数组中的下标
返回值：构造好的子树根节点

左子树节点数 = mid - in_left
左子树根的前序下标 = pre_left + 1
右子树根的前序下标 = pre_left + 1 + 左子树节点数

左子树中序范围：[in_left, mid)
右子树中序范围：[mid + 1, in_right)

class Solution:
    def buildTree(self, preorder, inorder):
        # 值不重复，因此每个值可以对应唯一的中序下标
        position = {value: i for i, value in enumerate(inorder)}

        def build(pre_left, in_left, in_right):
            if in_left >= in_right:
                return None

            root_value = preorder[pre_left]
            mid = position[root_value]
            left_size = mid - in_left

            node = TreeNode(root_value)
            node.left = build(pre_left + 1, in_left, mid)
            node.right = build(
                pre_left + 1 + left_size, mid + 1, in_right
            )
            return node

        return build(0, 0, len(inorder))

1. 我传入的是一个节点，还是一个数组区间？
2. 我希望这个函数返回整数、真假、节点，还是只向列表追加数据？
3. 空节点或空区间应该怎么处理？
4. 左右子树已经给出结果后，当前这一层怎么完成任务？

[[1, 2], [1, 3], [2, 3]]

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        nums = [i for i in range(1, n + 1)]
        result = []

        def backtrack(path, start_index):
            if len(path) == k:
                result.append(path[:])
                return

            for i in range(start_index, len(nums)):
                path.append(nums[i])
                backtrack(path, i + 1)
                path.pop()

        backtrack([], 0)
        return result

第一张拿 1：
    第二张拿 2 → 记下 [1, 2]
    把 2 放回去
    第二张拿 3 → 记下 [1, 3]
    把 3 放回去
把第一张 1 放回去

第一张拿 2：
    第二张拿 3 → 记下 [2, 3]
    把 3 放回去
把第一张 2 放回去

path   = 手里现在拿着哪些牌
result = 已经记下的完整组合

nums = [i for i in range(1, n + 1)]

nums = [1, 2, 3]
# 下标： 0  1  2

result = []

def backtrack(path, start_index):

backtrack([], 0)

if len(path) == k:
    result.append(path[:])
    return

for i in range(start_index, len(nums)):

path.append(nums[i])      # 选择当前数字
backtrack(path, i + 1)    # 探索这个选择下面的所有可能
path.pop()                # 探索结束，撤销当前选择

backtrack([], 0)

path.append(nums[0])  # path = [1]
backtrack(path, 1)

i = 1：加入 2，path = [1, 2]

result = [[1, 2]]

path.pop()  # 删除 2，path = [1]

i = 2：加入 3，path = [1, 3]

result = [[1, 2], [1, 3]]

path = [1]

path.pop()  # 删除 1，path = []

加入 2 → path = [2]
下一层只能从下标 2 开始
加入 3 → path = [2, 3]
保存 [2, 3]

加入 3 → path = [3]
后面没有数字可以继续选择，长度仍然只有 1
无法凑够 k = 2，因此不保存

result = [[1, 2], [1, 3], [2, 3]]

选择 → 递归探索 → 撤销选择

backtrack(path, i + 1)

i、start_index：每次调用各自拥有
path：多次调用共同修改同一个列表
result：所有调用共同向其中追加答案

1. path 表示当前已经做出的选择是什么？
2. 什么条件表示一个完整答案已经形成？
3. for 循环当前允许尝试哪些选择？
4. 递归调用后，为什么必须撤销当前选择？
5. 下一层从哪里开始，如何避免重复？

for 负责换着选择当前这一位；
递归负责继续选择下一位；
pop 负责从递归回来后撤销当前选择。