滑动窗口和双指针
分组循环
一种特殊情况的同向双指针,可以优化一个指针
适用场景
数组会被分割成若干组,每一组处理逻辑是相同的。
核心思想
外层循环负责遍历组之前的准备工作(记录开始位置),和遍历组之后的统计工作(更新答案最大值)。
内层循环负责遍历组,找出这一组最远在哪结束。
模板
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
题意很难懂,需要仔细理解。
首先要找的循环是严格字母序的,问题在于如何统计能避免重复。
这里有一个重要的观察是:如果开始是相同的字母,那么长的组合一定完全覆盖短的,组合的总数是长度。因此按照不同字母分组,每组取最长的累加起来就是答案。