滑动窗口和双指针


滑动窗口和双指针

分组循环

一种特殊情况的同向双指针,可以优化一个指针

适用场景

数组会被分割成若干组,每一组处理逻辑是相同的。

核心思想

外层循环负责遍历组之前的准备工作(记录开始位置),和遍历组之后的统计工作(更新答案最大值)。
内层循环负责遍历组,找出这一组最远在哪结束。

模板

n = len(nums)
i = 0
while i < n:
    start = i
    while i < n and ...:
        i += 1
    # 从 start 到 i-1 是一组
    # 下一组从 i 开始,无需 i += 1

题目

leetcode 978
需要连着看三个数保证子数组性质,相同的数需要跳过,注意最后答案的计算方式,最后答案可能包含位置i也可能不包含(越界)
leetcode 3255
先找出长度大于等于k的最长上升子数组,在里面再分组。因为已经保证是上升的,最大值即为每组最后一个元素。
如果没有这个前提条件,滑动窗口找最大值需要用单调双端队列维护。
leetcode 467
题意很难懂,需要仔细理解。
首先要找的循环是严格字母序的,问题在于如何统计能避免重复。
这里有一个重要的观察是:如果开始是相同的字母,那么长的组合一定完全覆盖短的,组合的总数是长度。因此按照不同字母分组,每组取最长的累加起来就是答案。

未完待续...