尺取法

8 分钟

尺取(滑窗)维护区间 [l,r],右指针扩张纳入元素,当条件满足(或超标)时左指针收缩。适合“最短/最长满足某和某条件的连续子段”,每个元素进出各一次,O(n)。

小纸条

尺取法中每个元素最多被 l、r 各访问几次?

登录 后可看答案

尺取法 · 算法进阶 · op599 课程