LeetCode训练day5-滑动窗口

手机软件开发 · 2024-10-1 23:19:28

滑动窗口（Sliding Window）

滑动窗口指的是如许一类题目标求解方法，在数组上通过双指针同向移动而办理的一类题目。着实如许的题目我们可以不必为它们专门定名一个名字，它们的解法着实是很自然的。
使用滑动窗口办理的题目通常是暴力解法的优化，把握这一类题目最好的办法就是训练，然后思考清晰为什么可以使用滑动窗口。

滑动：窗口可以按照肯定的方向移动。
窗口：窗口巨细可以固定，也可以不固定，此时可以向外大概向内，扩容大概缩小窗口直至满足条件。

先容

滑动窗口是一种办理题目标思绪和方法，通常用来办理一些连续题目。好比 LeetCode 的 209. 长度最小的子数组。更多滑动窗口题目见下方题目列表。
常见套路

滑动窗口主要用来处理处罚连续题目。好比题目求解“连续子串 xxxx”，“连续子数组 xxxx”，就应该可以想到滑动窗口。能不能办理另说，但是这种敏感性还是要有的。
从范例上说主要有：

固定窗口巨细
窗口巨细不固定，求解最大的满足条件的窗口
窗口巨细不固定，求解最小的满足条件的窗口（上面的 209 题就属于这种）

背面两种我们统称为可变窗口。固然不管是哪种范例根本的思绪都是一样的，不一样的仅仅是代码细节。
办理滑动窗口题目标根本步调

滑动窗口更像是一种技能而不是一种算法。这是一种可以在许多算法中使用的技能。以下是办理与滑动窗口技能相干的题目标根本步调：使用 hashmap 或字典来盘算特定的数组输入并坚持使用外部循环向右增长窗口。在外部循环下，使得滑动窗口左侧向右滑动来维持窗口巨细。使用这种方式低沉循环次数根据题目报告存储当前的最大或最小窗口巨细或计数。
固定窗口巨细

对于固定窗口，我们只需要固定初始化左右指针 l 和 r，分别表现的窗口的左右顶点，而且包管：

l 初始化为 0
初始化 r，使得 r - l + 1 便是窗口巨细
同时移动 l 和 r
判定窗口内的连续元素是否满足题目限定的条件
- 4.1 假如满足，再判定是否需要更新最优解，假如需要则更新最优解
- 4.2 假如不满足，则继续。

可变窗口巨细

对于可变窗口，我们同样固定初始化左右指针 l 和 r，分别表现的窗口的左右顶点。背面有所差别，我们需要包管：

l 和 r 都初始化为 0
r 指针移动一步
判定窗口内的连续元素是否满足题目限定的条件
- 3.1 假如满足，再判定是否需要更新最优解，假如需要则更新最优解。并实行通过移动 l 指针缩小窗口巨细。循环实行 3.1
- 3.2 假如不满足，则继续。

形象地来看的话，就是 r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口紧缩的效果。
模板代码

伪代码

初始化慢指针 = 0初始化 ansfor 快指针 in 可迭代聚集更新窗口内信息 while 窗口内不符合题意扩展大概紧缩窗口慢指针移动更新答案返回 ans

LeetCode训练day5-滑动窗口

所属分类: 问答交流

新帖推荐: 30日

推荐作品