白板思路整理Part1. 两数之和（1），数组/哈希/前缀和，遍历 + 回看历史
- 确认题目含义
- 输入类型
- 输出类型
- 空输入如何处理
- 是否必定有解
一些话术：“题目保证数组长度至少为 2，且一定有唯一解，所以我不做空数组和无解处理。”
边界上
一些话术：“输入保证满足这些约束，不需要校验”
白板不一定会预先给出接口，需主动问或自己定义并说明假设
举一个例子（这里以题号为1的two sum为例）
一些话术：“如输入 nums = [2,7,11,15], target = 9，返回 [0,1]，因为 2+7=9”
例子不需要复杂，能说明问题即可
先说暴力解，再说优化
一些话术：“最直接是两层循环，枚举所有配对，时间复杂度 O(n²)。我想优化到 O(n)，用哈希表存已经遍历过的值和下标，遍历时查 target - num 是否存在”
时间/空间复杂度的计算：
时间复杂度 看基本操作执行次数随 n 怎么增长，取最高阶，去常数
空间复杂度 看额外开辟的内存随 n 怎么增长；输入 nums、输出结果不算额外空间
以tow sum的暴力解为例，
def twoSum(nums, target):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
时间复杂度的计算，如下：
外层循环 i 走 n 次。
内层 j 从 i+1 到 n-1：
i=0：比较 n-1 次
i=1：比较 n-2 次
i=2：比较 n-3 次
…
i=n-2：比较 1 次，即为(n−1)+(n−2)+⋯+1= n(n−1)/2
将等式展开，去掉常数、低阶项，只保留最高阶后，得到O(n²)，因此暴力解的时间为O(n²)
空间复杂度的计算，如下：
只用了 i、j、n、target 这些常数个变量。
没有额外数组、哈希表、递归栈。
所以额外空间：O(1)。
在暴力解的基础上进行时间/空间优化，尝试enumerate 哈希解
def twoSum(nums, target):
seen = {}，创建一个空字典，其中key为已经遍历过的数值，value为该数值对应的下标
for i, num in enumerate(nums):，enumerate(nums) 是迭代器，每次产生一个 (下标, 元素) 对。i为当前元素的下标，num为当前元素的值。它不会复制整个 nums，所以不额外占 O(n) 空间
need = target - num，为了和当前 num 相加等于 target，需要的另一个数是 need
if need in seen:，在字典里查找 need 是否存在，哈希查找平均 O(1)
return [seen[need], i]，如果存在，seen[need] 是之前那个数的下标，i 是当前数的下标。直接返回这两个下标。
seen[num] = i，如果 need 不存在，就把当前数和下标存进字典，供后面的元素查找
return []，题目保证有解，所以理论上不会走到这里。但为了代码完整，最后返回空列表。
时间复杂度的计算，如下：
循环执行 n 次，每次做两件事：
need in seen：哈希查找，平均 O(1)
seen[num] = i：哈希插入，平均 O(1)
所以每次循环平均是 O(1)。
总共 n 次，有n×O(1)=O(n)。所以平均时间复杂度：O(n)
注，严格来说，哈希表最坏情况下冲突严重，查找/插入可能退化到 O(n)，总时间最坏是 O(n²)
但面试和工程里通常说 Python dict 平均 O(1)，所以答：平均 O(n)，最坏 O(n²)
再注，哈希表查找平均 O(1)，靠的前提是：哈希函数把 key 均匀地散列到不同桶里，冲突很少。那么，一旦所有 key 都挤到同一个桶，查找就退化成“遍历一个链表/数组”，也就是 O(n)
空间复杂度的计算，如下
seen 字典最多存 n 个键值对：
- key：数组里的数
- value：下标
所以额外空间：O(n)
enumerate 本身是迭代器，不会复制整个 nums，所以它不额外增加 O(n) 空间。此处的空间复杂度 O(n) 完全来自 seen 字典
注，enumerate、zip、map、filter 返回的是迭代器
写代码前确认方案
一些话术：“我打算用一个哈希表 seen，key 是数值，value 是下标。遍历数组，先查 target - num 是否在 seen 里，如果在就返回；否则把当前值和下标存进去。”
并积极询问，是否可以开始手写coding
边写边讲
一些话术：“这里 i 是当前下标，need = target - num。
先查后存，是为了处理 [3,3], target=6 这种情况，避免同一个元素用两次。”
代码要命名清晰，边界检查要写出来
写完手动跑样例
白板没有运行按钮，所以必须自己跑。
一些话术：“我用刚才的例子走一遍：i=0，num=2，need=7，不在 seen，存 2:0；
i=1，num=7，need=2，在 seen，返回 [0,1]。”
再补边界：
“空数组返回空；无解返回空；重复元素先查后存可以处理。”
说复杂度
最后做出总结。
一些话术：“时间复杂度 O(n)，空间复杂度 O(n)。”
如果能优化空间，也可以提一句，但不要强行炫技。
面试中，将以上1-7点以结构化展现
卡住时怎么办？
不要沉默。说一些话术：
“我目前想到两种方向：一是……二是……我倾向第二种，因为……但这里有个卡点，是……”
对方通常会给提示。你接住提示继续推进，也是加分项
偏工程岗的白板重点
代码可读性：命名清晰，别写 a,b,c
边界完整：空、单元素、重复、无解
能自测：写完主动跑例子
沟通自然：边写边解释，别背题
不追求炫技：正确、清晰、可维护 > 奇技淫巧
白板思路整理Part2. 和为 K 的子数组（560），数组/哈希/前缀和，遍历 + 回看历史
- 确认题目信息
“题目是：给一个整数数组 nums 和一个整数 k，统计并返回和等于 k 的连续子数组的个数。
注意是连续子数组，不是子序列。
数组可能有负数，可能有重复，可能为空。
我确认一下：子数组必须是连续的，元素顺序不变。
返回的是个数，不是具体子数组。
数组里可能有负数，所以不能用滑动窗口。”
假设面试官确认：有负数，返回个数。
- 举个小例子
nums = [1, 1, 1], k = 2
手动找和为 2 的连续子数组：
- [1, 1]（下标 0-1）
- [1, 1]（下标 1-2）
所以返回 2。
- 暴力解与优化方向
最直接是枚举所有子数组，两层循环，固定起点，累加终点，判断和是否等于 k。
时间 O(n²)，空间 O(1)。
但我们可以用前缀和优化。”
“先定义前缀和：prefix[i] 表示 nums[0] 到 nums[i-1] 的和。
那么子数组 nums[i..j] 的和等于 prefix[j+1] - prefix[i]。
要求 prefix[j+1] - prefix[i] = k，移项得 prefix[i] = prefix[j+1] - k。”
“这和 1 两数之和是同一个模板：
遍历 + 回看历史。
1 是 need = target - num，查历史有没有 need。
560 是 need = current_sum - k，查历史有多少个 need。
区别：1 找到就 return，560 要累加计数。”
- 手写代码时详解
from typing import List
import collections
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count = collections.defaultdict(int)
count[0] = 1
current_sum = 0
ans = 0
for num in nums:
current_sum += num
need = current_sum - k
ans += count[need]
count[current_sum] += 1
return ans
“count = collections.defaultdict(int)。
key 是前缀和，value 是这个前缀和出现的次数。
用 defaultdict(int)，不存在的 key 默认返回 0，省去判断。”
“count[0] = 1。
这是关键初始化。
前缀和 0 表示“一个元素都没选”的状态，出现 1 次。
它的作用是处理从下标 0 开始的子数组。
比如 nums = [1, 1], k = 2，遍历到第二个 1 时，current_sum = 2，need = 0，
如果 count[0] 不存在，就会漏掉 [1, 1] 这个子数组。”
“current_sum = 0，ans = 0。”
“遍历 nums 里的每个 num：
current_sum += num，更新当前前缀和。
need = current_sum - k，需要的历史前缀和。
ans += count[need]，历史上有多少个前缀和等于 need，就有多少个子数组以当前位置结尾且和为 k。
count[current_sum] += 1，把当前前缀和记录进历史。”
“注意顺序：先查后存。
和 1 一样，先查历史，再记录当前。
这样避免把当前元素自己算进去。”
“最后返回 ans。”
- 用例子验证代码
nums = [1, 1, 1], k = 2
初始化：count = {0: 1}, current_sum = 0, ans = 0
步骤 num current_sum need count[need] ans count 更新
1 1 1 -1 0 0 {0:1, 1:1}
2 1 2 0 1 1 {0:1, 1:1, 2:1}
3 1 3 1 1 2 {0:1, 1:1, 2:1, 3:1}
返回 2。正确。
再验证 nums = [1, -1, 0], k = 0：
初始化：count = {0: 1}, current_sum = 0, ans = 0
步骤 num current_sum need count[need] ans count 更新
1 1 1 1 0 0 {0:1, 1:1}
2 -1 0 0 1 1 {0:2, 1:1}
3 0 0 0 2 3 {0:3, 1:1}
返回 3。对应子数组：[1,-1]、[0]、[1,-1,0]。正确。
边界验证：
nums = [] → 循环不执行，返回 0。正确。
nums = [1], k = 0 → current_sum = 1, need = 1, count[1] = 0, ans = 0。正确。
nums = [1], k = 1 → current_sum = 1, need = 0, count[0] = 1, ans = 1。正确。
- 总结复杂度
“时间复杂度：
遍历一次数组，O(n)。
每次哈希查找和插入平均 O(1)。
总时间平均 O(n)。
最坏情况哈希冲突严重时 O(n²)，但通常说平均 O(n)。”
“空间复杂度：
count 最多存 n+1 个前缀和，O(n)。
总空间 O(n)。”
- 面试收尾话术
“这题就写完了。
核心是把子数组和转化为两个前缀和之差，然后用哈希表统计历史前缀和出现的次数。
它和 1 两数之和是同一个模板：遍历 + 回看历史。
1 是找唯一解直接 return，560 是统计所有解累加计数。
时间平均 O(n)，空间 O(n)。
关键细节是 count[0] = 1 的初始化，处理从下标 0 开始的子数组。”
===========================================================
白板思路整理Part3. 字母异位词分组（49），数组/哈希/前缀和，预处理 + 构造 key / 去重 / 存在性
- 确认题目含义
- 输入类型
- 输出类型
- 空输入如何处理
- 是否必定有解
一些话术：“我确认一下：返回顺序不重要，分组内顺序也不重要。数组可能为空吗？字符串只包含小写字母吗？如果只包含小写字母，可以用计数法；如果不限定，排序法更通用。”
举个小例子
输入strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]，手动分组
结果是[[“eat”,”tea”,”ate”], [“tan”,”nat”], [“bat”]]
横比计数 / 排序，简单提及计数解法
这一环节比较其他思路的解法/无优化解法。
一些话术：
“这题核心是：怎么给同一组异位词生成一个相同的 key。
有两种常见做法：
一是排序法：把字符串排序，异位词排序后一定相同。
二是计数法：统计每个字符出现次数，转成元组作为 key。
计数法理论时间 O(n·k)，排序法 O(n·k log k)，计数法更优。
但计数法只适合小写字母这种固定小字符集，而且 Python 里统计频次是纯 Python 循环，常数大。
排序用的是 C 实现的 Timsort，字符串通常很短，实际往往更快。
所以我优先写排序法，通用且白板不易错。”
“n：字符串数组 strs 的长度，k：每个字符串的平均长度。”
“时间复杂度：每个字符串长度 k，排序 O(k log k)，拼接 O(k)，哈希插入平均 O(1)，一共 n 个字符串，所以总时间 O(n·k log k)。
空间复杂度：哈希表要存 n 个排序后的 key，总字符数 O(n·k)，所以额外空间 O(n·k)。
如果字符串长度不一，用 Σ k_i log k_i 表示时间，空间是 Σ k_i。”
注，Timsort，平均和最坏都是 O(k log k)。
sorted 会返回一个新列表，长度 k，所以额外空间是： O(k)
- 手写代码时详解
from typing import List
import collections
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mp = collections.defaultdict(list)
`for st in strs:`
`key = "".join(sorted(st))`
`mp[key].append(st)`
`return list(mp.values())`
mp = collections.defaultdict(list)，defaultdict 的参数是一个默认工厂函数，这里传 list。意思是：当我访问一个不存在的 key 时，自动创建一个空列表作为默认值，省去判断。注意，这里的 list 是无参可调用的，list() 得到 []。如sorted”eat”后，得到”aet”，而mp[“aet”]不存在，此时工厂函数会自动创建 []
for st in strs: 遍历 strs 里的每个字符串 st
key = “”.join(sorted(st))，sorted(st) 返回排序后的字符列表，比如 sorted(“eat”) 得到 [‘a’,’e’,’t’]。””.join(…) 把它拼回字符串 “aet”。异位词排序后一定相同，所以这个 key 能把它们分到一组。
mp[key].append(st)， 如果 key 不存在，defaultdict 自动创建空列表，然后 append(st) 把原字符串加进去。注意，存进 value 的是原字符串 st，不是 key。
return list(mp.values())，mp.values() 返回的是 dict_values 视图，不是列表。要求返回 List[List[str]]，所以用 list() 转一下
- 再给出一个例子简单验证代码
用 strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 走一遍。
最后返回：
list(mp.values()) # [[“eat”,”tea”,”ate”], [“tan”,”nat”], [“bat”]]
边界验证：
空数组：strs = []，循环不执行，mp = {}，返回 []。正确。
单字符串：strs = [“a”]，返回 [[“a”]]。正确。
重复字符串：strs = [“a”,”a”]，key 都是 “a”，返回 [[“a”,”a”]]。正确。
- 总结复杂度
“时间复杂度：
每个字符串长度平均为 k，排序需要 O(k log k)。
一共 n 个字符串，所以总时间 O(n · k log k)。
哈希表插入和查找平均 O(1)，不改变总复杂度。”
“空间复杂度：
哈希表存了所有字符串，共 n 个，每个长度 k，所以 O(n · k)。
另外 key 也存了 n 个，长度 k，但和字符串本身同阶，不改变复杂度。
所以总空间 O(n · k)。”
“如果面试官追问优化：
可以用计数法，把长度 26 的频次数组转成元组作为 key，时间 O(n · k)，空间 O(n · k)。
但只适合固定小字符集，Python 中实际常数更大，所以我优先排序法。”
- 面试收尾话术
“这题就写完了。
核心是用排序后的字符串作为 key，把异位词映射到同一组。
时间 O(n · k log k)，空间 O(n · k)”
白板思路整理Part4. 最长连续序列（128），数组/哈希/前缀和，预处理 + 构造 key / 去重 / 存在性
确认题目信息
“题目是：给一个未排序的整数数组 nums，找出数字连续的最长序列的长度。
注意，连续序列不要求在原数组里下标连续，只要求数值连续。
比如 [100, 4, 200, 1, 3, 2]，最长连续序列是 1, 2, 3, 4，长度 4。
数组可能有重复元素，可能为空。
我确认一下：是否要求 O(n) 时间？如果有重复，是否只算一次？
通常这题要求 O(n)，重复数字不影响连续长度。”
假设面试官确认：要求 O(n)，重复数字只算一次。
举个小例子
nums = [100, 4, 200, 1, 3, 2]
手动找连续序列：
1, 2, 3, 4 是连续的，长度 4
100 单独，长度 1
200 单独，长度 1
所以返回 4。
暴力解与优化方向
“最直接的做法有两种：
一是排序后扫描，时间 O(n log n)，空间 O(1) 或 O(n)。
二是对每个数，不断用线性查找找 x+1、x+2，时间 O(n²) 或更差。
但题目要求 O(n)，所以需要用哈希表做 O(1) 存在性判断。
我们可以用 set 存储所有数字，顺便去重。
然后只从连续序列的起点开始向后数，保证每个元素最多访问一次。”
手写代码时详解
from typing import List
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
longest_streak = 0
num_set = set(nums)
`for num in num_set:`
`if num - 1 not in num_set:`
`current_num = num`
`current_streak = 1`
`while current_num + 1 in num_set:`
`current_num += 1`
`current_streak += 1`
`longest_streak = max(longest_streak, current_streak)`
`return longest_streak`
逐行讲：
“第一行，longest_streak = 0，记录全局最长长度。”
“num_set = set(nums)。
把数组转成集合，一是去重，二是提供 O(1) 的存在性判断。
set 底层是哈希表，in 平均 O(1)。”
“然后遍历 num_set，不是遍历原数组。
因为去重后每个数字只处理一次，避免重复计算。”
“if num - 1 not in num_set:
这是关键优化：只从连续序列的起点开始数。
如果 num - 1 存在，说明 num 不是起点，跳过，留给它的前驱去扩展。
这样每个数字最多被访问一次。”
“如果 num 是起点，初始化：
current_num = num，表示当前序列的末尾数字。
current_streak = 1，起点本身算一个。”
“while current_num + 1 in num_set:
检查下一个数字是否在集合里。
如果在，就把 current_num 推进到下一个数字，长度加 1。
注意必须 current_num += 1，否则会死循环。”
“循环结束后，current_streak 就是以 num 为起点的连续序列长度。
用 max 更新全局最长长度。”
“最后返回 longest_streak。”
- 用例子验证代码
nums = [100, 4, 200, 1, 3, 2]
num_set = {1, 2, 3, 4, 100, 200}
遍历 num_set：
num num-1 在集合？ 操作
1 0 不在 起点。current=1, streak=1；检查 2 在 → current=2, streak=2；检查 3 在 → current=3, streak=3；检查 4 在 → current=4, streak=4；检查 5 不在，停止。longest=4
2 1 在 不是起点，跳过
3 2 在 跳过
4 3 在 跳过
100 99 不在 起点。检查 101 不在，streak=1，longest 仍为 4
200 199 不在 起点。检查 201 不在，streak=1，longest 仍为 4
最终返回 4。正确。
边界验证：
nums = [] → num_set = set()，循环不执行，返回 0。正确。
nums = [1] → num_set = {1}，1-1=0 不在，起点，1+1=2 不在，streak=1，返回 1。正确。
nums = [1,1,2,2] → num_set = {1,2}，遍历到 1 时，0 不在，起点，检查 2 在，streak=2，返回 2。正确。
- 总结复杂度
“时间复杂度：
构建 set 是 O(n)。
遍历 set 是 O(n)。
内层 while 虽然看起来像循环，但每个数字最多作为某个连续序列的一部分被访问一次。
因为只有起点才会进入 while，而非起点会被跳过。
所以总时间平均 O(n)。
注意哈希查找平均 O(1)，最坏 O(n)，但通常说平均 O(n)。”
“空间复杂度：
num_set 存储所有不重复数字，最多 n 个，所以 O(n)。
其他变量是常数级。
总空间 O(n)。”
- 面试收尾话术
“这题就写完了。
核心是用 set 做 O(1) 存在性判断，并且只从连续序列的起点开始向后数，保证每个元素只访问一次。
时间平均 O(n)，空间 O(n)。
如果面试官追问，也可以用排序法 O(n log n) 做，但哈希法更符合 O(n) 要求。”
白板思路整理Part5. 前 K 个高频元素 （347），栈/二分/基础结构，预处理 + 构造 key / 去重 / 存在性
确认题目信息
“题目是：给一个整数数组 nums 和一个整数 k，返回出现频率最高的 k 个元素。
返回顺序不重要。
题目保证答案唯一，也就是不会出现频率相同、需要二选一的情况，或者即使有，任意顺序都可以。
我确认一下：k 一定合法，1 ≤ k ≤ 不同元素个数。
数组可能为空吗？通常不会，k 至少是 1。”
举个小例子
nums = [1, 1, 1, 2, 2, 3], k = 2
统计频率：
1 出现 3 次
2 出现 2 次
3 出现 1 次
频率最高的 2 个是 1 和 2。
返回 [1, 2] 或 [2, 1] 都行。
暴力解与优化方向
“最直接的做法：
先用哈希表统计频率，O(n)。
然后把所有 (数字, 频率) 按频率排序，取前 k 个。
排序是 O(m log m)，m 是不同元素个数。
总时间 O(n + m log m)，空间 O(m)。
这个解法够用，但如果 m 很大、k 很小，排序有点浪费。
优化方向：只维护前 k 个，不需要全排序。
用最小堆维护当前频率最高的 k 个，堆大小始终 ≤ k。
时间 O(n + m log k)，空间 O(m)。”
手写代码时详解
from collections import Counter
import heapq
class Solution:
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
freq = Counter(nums)
min_heap = []
for num, count in freq.items():
if len(min_heap) < k:
heapq.heappush(min_heap, (count, num))
else:
if count > min_heap[0][0]:
heapq.heapreplace(min_heap, (count, num))
return [num for _, num in min_heap]
逐行讲：
“freq = Counter(nums)。
统计每个数字出现的次数，返回一个字典，key 是数字，value 是频率。
比如 {1: 3, 2: 2, 3: 1}。”
“min_heap = []。
准备一个最小堆，用来维护当前频率最高的 k 个元素。
堆里存 (count, num) 元组，第一个是频率，第二个是数字。
为什么频率在前？因为 Python 元组比较先比第一个元素，堆要按频率排序。”
“for num, count in freq.items()。
遍历每个数字和它的频率。
注意这里是 num, count，和堆里存的 (count, num) 顺序相反，别搞混。”
“if len(min_heap) < k:
堆还没满，直接压入 (count, num)。
heappush 会自动维护最小堆性质，O(log k)。”
“else:
堆已经满了。
if count > min_heap[0][0]:
min_heap[0] 是堆顶，即当前 k 个里频率最小的。
min_heap[0][0] 是它的频率。
如果当前数字频率比堆顶频率大，说明堆顶不配留在前 k，淘汰它。”
“heapq.heapreplace(min_heap, (count, num))。
弹出堆顶，压入当前元素，一次完成，O(log k)。
等价于先 heappop 再 heappush，但更快。”
“return [num for _, num in min_heap]。
堆里存的是 (count, num)。
用 _ 忽略频率，只取数字，组成答案列表。
返回顺序不重要。”
- 用例子验证代码
nums = [1, 1, 1, 2, 2, 3], k = 2
freq = {1: 3, 2: 2, 3: 1}
初始化：min_heap = []
步骤 num count 堆状态 操作
1 1 3 [(3,1)] len < 2，push
2 2 2 [(2,2), (3,1)] len < 2，push
3 3 1 [(2,2), (3,1)] len == 2，1 > 2？否，跳过
最终堆：[(2,2), (3,1)]
返回 [2, 1] 或 [1, 2]，正确。
再验证 nums = [1, 2], k = 2：
freq = {1: 1, 2: 1}
步骤 num count 堆状态
1 1 1 [(1,1)]
2 2 1 [(1,1), (1,2)]
返回 [1, 2]。正确。
边界验证：
nums = [1], k = 1 → freq = {1: 1}，堆 [(1,1)]，返回 [1]。正确。
nums = [1,1,1], k = 1 → 堆只保留频率最高的 1，返回 [1]。正确。
- 总结复杂度
“时间复杂度：
统计频率 Counter(nums)：O(n)。
遍历不同元素 m 个，每个最多一次堆操作，O(log k)。
总时间：O(n + m log k)。
如果 k 接近 m，退化成 O(n + m log m)，和排序差不多。
但 k 小时，堆更快。”
“空间复杂度：
freq 哈希表存 m 个元素：O(m)。
min_heap 最多 k 个元素：O(k)。
总空间：O(m)。”
面试收尾话术
“这题分两步：先用 Counter 统计频率，再用最小堆维护频率最高的 k 个。
堆里存 (频率, 数字)，堆顶是当前 k 个里频率最小的，方便淘汰。
时间 O(n + m log k)，空间 O(m)。
如果面试官问有没有 O(n) 解法，可以用桶排序：频率作为桶下标，从高到低取 k 个。”
补充：桶排序 O(n) 解法（面试追问时提）
“如果频率范围不大，可以用桶排序：
建一个长度为 n+1 的数组，下标是频率，值是出现该频率的数字列表。
然后从高到低遍历桶，取够 k 个就停。
时间 O(n)，空间 O(n)。
但堆解法更通用，不依赖频率范围，所以我优先写堆。”
===========================================================
白板思路整理Part6. 盛最多谁的容器 （11），双指针/滑动窗口，预处理 + 构造 key / 去重 / 存在性
确认题目信息
“题目是：给一个整数数组 height，每个元素代表一条垂线的高度。
选两条线，和 x 轴组成一个容器，求能装最多水的面积。
面积 = 两条线之间的距离 × 两条线中较短的那条高度。
也就是 min(height[l], height[r]) * (r - l)。
我确认一下：数组长度至少为 2，高度非负。
不能倾斜容器，所以宽度就是下标差。”
举个小例子
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
最大面积来自下标 1 和下标 8：
高度：min(8, 7) = 7
宽度：8 - 1 = 7
面积：7 × 7 = 49
返回 49。
暴力解与优化方向
“最直接是枚举所有左右两条线，两层循环，计算面积，取最大。
时间 O(n²)，空间 O(1)。
优化方向：用双指针从两端向中间夹逼。
初始宽度最大，然后每次移动高度较小的那一侧，因为面积由短边决定。
移动长边没有意义：短边不变或更短，宽度还变小，面积不可能变大。
所以只移动短边，期待遇到更高的边，从而可能增大面积。
时间 O(n)，空间 O(1)。”
手写代码时详解
from typing import List
class Solution:
def maxArea(self, height: list[int]) -> int:
l, r = 0, len(height)-1
ans = 0
while l < r:
area = min(height[l], height[r]) * (r-l)
ans = max(ans, area)
if height[l] <= height[r]:
l += 1
else:
r -= 1
return ans
逐行讲：
“l = 0，r = len(height) - 1。
左右指针分别指向数组两端，初始宽度最大。”
“ans = 0。
记录全局最大面积。”
“while l < r:
当左右指针没有相遇时，继续计算。”
“容器的高度由较短的那条线决定，水会从短边溢出。”
“area = min(height[l], height[r]) * (r-l)。
当前面积。”
“ans = max(ans, area)。
更新全局最大面积。”
“if height[l] <= height[r]: left += 1
else: right -= 1
关键：移动高度较小的一侧。
如果左边短，就左指针右移；否则右指针左移。
相等时移动哪边都可以，这里用 else 移动右边。”
“最后返回 ans。”
- 用例子验证代码
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
初始化：left = 0, right = 8, max_water = 0
步骤 left right 高度 宽度 面积 max_water 移动
1 0 8 min(1,7)=1 8 8 8 左短，left++
2 1 8 min(8,7)=7 7 49 49 右短，right–
3 1 7 min(8,3)=3 6 18 49 右短，right–
4 1 6 min(8,8)=8 5 40 49 相等，right–
… … … … … … 49 继续
最终 max_water = 49。正确。
边界验证：
height = [1, 1] → 面积 1 × 1 = 1，返回 1。
height = [4, 3, 2, 1, 4] → 最大面积下标 0 和 4：min(4,4) × 4 = 16。
全相等：任意两边面积相同，双指针会逐步缩小，结果正确。
- 总结复杂度
“时间复杂度：
双指针从两端向中间移动，每个元素最多被访问一次。
总共移动 n - 1 次，所以时间 O(n)。”
“空间复杂度：
只用了 l、r、area、ans 几个变量。
没有额外数组或哈希表。
所以空间 O(1)。”
- 面试收尾话术
“这题用双指针夹逼。
初始宽度最大，每次移动高度较小的一侧，因为面积由短边决定。
移动长边不会让面积变大，所以只移动短边。
时间 O(n)，空间 O(1)。
这是双指针夹逼的典型题，和 15 三数之和、42 接雨水有相似的收缩思想。”
===========================================================
少量数据结构八股
- 堆的八股
- 堆是一棵完全二叉树。
- 最小堆（parent节点 ≤ child节点）、最大堆（parent节点 ≥ child节点）
- 堆顶是全局最小/最大，但堆内其他元素不保证有序
- 底层实现
- 用数组存，不用指针。
- 下标关系：parent: i，left child: 2i+1，right child: 2i+2。
- child: i，parent: (i-1)//2。
- 所以堆是“逻辑上是树，物理上是数组
- 核心操作与复杂度
- 获取堆顶：O(1)
- 插入（push）：放到数组末尾，然后上浮，O(log n)
- 删除堆顶（pop）：把末尾元素放到堆顶，然后下沉，O(log n)
- 建堆（heapify）：从最后一个非叶子节点开始下沉，O(n)
- 堆排序：建堆 + 反复弹出堆顶，O(n log n)
- Python 的 heapq
- 默认是最小堆。
- 只有 heappush、heappop、heapreplace、heapify。
- 没有最大堆，要最大堆就把元素取负，或存 (-freq, num)。
- heapq 不是线程安全的。
- 底层是 list，heap[0] 是堆顶。
- 和平衡树的区别
- 堆只保证堆顶最值，不保证整体有序。
- 平衡树整体有序，支持范围查询、前驱后继。
- 堆插入/删除 O(log n)，取最值 O(1)，比平衡树简单。
- 需要“只取最值”用堆；需要“有序遍历”用平衡树。