LC763
划分字母区间
贪心 · 划分字母区间可视化:贪心串划分最多段,每段含某字母仅在该段。
时间 O(n)空间 O(1)
题目1 / 14
题目与输入建立输入、目标与算法心智
扫描扩展 end,到达 end 时切一段
正在加载算法场景...
当前发生了什么
串划分最多段,每段含某字母仅在该段。
机器状态
last 位置、start/end。
为什么正确
记录每字母最后位置;扫描维护当前段 end, i==end 切段。
不变量
段 end 必须是段内所有字母 last 的最大值。
面试怎么说
贪心 O(n)。
人类输入
串划分最多段,每段含某字母仅在该段。
机制
记录每字母最后位置;扫描维护当前段 end, i==end 切段。
机器状态
last 位置、start/end。
可观察结果
划分段列表。
不变量
- · 段 end 必须是段内所有字母 last 的最大值。
常见误区
- · i 到达 end 才能切。
迁移练习
- · LC56 合并区间
- · LC435 无重叠
面试怎么答
贪心 O(n)。