前言

使用语言 Python, 只针对 LC Medium 和 Hard 题, 面向面试刷题
Note: 除非你面前端 (加上 JS) , 否则统一使用 Python 进行刷题

基本操作

# 创建
nums = []
nums = [1, 2, 3]
nums = [0] * 5          # [0, 0, 0, 0, 0]

# 访问
nums[0]                 # 第一个
nums[-1]                # 最后一个
nums[1:3]               # [1, 3) 切片
nums[::-1]              # 反转

parts = ['', 'a', 'b', 'c']
parts[:-1]   # ['', 'a', 'b']  去掉最后一个

# 排序列表
nums = [3, 1, 2]
sorted(nums)         # [1, 2, 3]，原 nums 不变

# 降序
sorted(nums, reverse=True)  # [3, 2, 1]

# enumerate（同时拿 index 和值）
for i, num in enumerate(nums):
    print(i, num)

# zip（同时遍历多个 list）
for a, b in zip(list1, list2):
    print(a, b)
# 末尾操作
nums.append(4)          # 加到末尾，O(1)
nums.pop()              # 删除末尾，O(1)

# 指定位置
nums.insert(0, 9)       # 在 index 0 插入，O(n)
nums.pop(0)             # 删除 index 0，O(n)

# 删除特定值
nums.remove(3)          # 删除第一个值为 3 的元素，O(n)

# 清空
nums.clear()

题目

LC 252

LC 2672

维护相邻相同颜色的 pair 数量，每次 query 先尝试移除 index i 之前可能形成的 pair，更新颜色，再尝试添加更新后的新 pair

LC 845

维护两个 list (up, down)，up[i] 表示以 i 结尾的最长严格上坡长度，down[i] 表示以 i 开始的最长严格下坡长度，然后遍历数组找 up[i] > 0 and down[i] > 0 的峰顶，最大 mountain 长度就是 up[i] + down[i] + 1

LC 56

每次和结果列表的最后一个区间比较: 如果重叠就更新右端点，否则直接加入结果

LC 2021

对每盏灯生成区间事件 (start, +1) 和 (end+1, -1)，按位置排序，然后扫事件累加亮度，更新最大亮度及对应最小位置

events.append((start, +1))   # 区间开始，亮度增加
events.append((end+1, -1))   # 区间结束后，亮度减少

灯1: [2, 5] → positions 2 3 4 5 brightness +1
灯2: [4, 6] → positions 4 5 6 brightness +1

pos 4 → 被两盏灯覆盖 → brightness = 2
pos 5 → 被两盏灯覆盖 → brightness = 2

LC 57

先把所有在新区间左边且不重叠的加入结果，中间把所有与新区间重叠的区间合并成一个，最后把右边剩余区间直接追加

LC 581

从左往右维护最大值找最右乱序位置，从右往左维护最小值找最左乱序位置，这两个边界之间就是最短需要排序的子数组

nums = [2, 6, 4, 8, 10, 9, 15]

右边界：4 < 6 → r = 2，9 < 10 → r = 5  
左边界：10 > 9 → l = 4，6 > 4 → l = 1  

区间 = nums[1..5] = [6, 4, 8, 10, 9]
答案 = 5