feat: 滑动窗口

lucifer · lucifer · commit 255799db3c40 · 2020-03-16T21:43:07.000+08:00
diff --git a/README.md b/README.md
@@ -285,6 +285,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [《构造二叉树》专题](https://lucifer.ren/blog/2020/02/08/%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%93%E9%A2%98/) 🆕
 - [《贪婪策略》专题](./thinkings/greedy.md) 🆕
 - [《深度优先遍历》专题](./thinkings/DFS.md) 🆕
+- [滑动窗口（思路 + 模板）](./thinkings/slide-window.md) 
 
 ### anki 卡片
 
@@ -330,12 +331,14 @@ anki - 文件 - 导入 - 下拉格式选择“打包的 anki 集合”，然后
 
 - LeetCode 换皮题目集锦
 
-- 滑动窗口（思路 + 模板）#3 #76 #209 #438 #862 #904 #930 #992  #1004 #1234 #1248
-
 - 动态规划完善。最长递增子序列，最长回文子序列，编辑距离等“字符串”题目， 扔鸡蛋问题。 解题模板，滚动数组。
 
 - 堆可以解决的题目。 手写堆
 
+- 单调栈
+
+- 设计题
+
 ## 关注我
 
 我重新整理了下自己的公众号，并且我还给它换了一个名字`脑洞前端`，它是一个帮助你打开大前端新世界大门的钥匙 🔑，在这里你可以听到新奇的观点，看到一些技术尝新，还会收到系统性总结和思考。
diff --git a/thinkings/slide-window.md b/thinkings/slide-window.md
@@ -0,0 +1,85 @@
+# 滑动窗口（Sliding Window）
+
+笔者最早接触滑动窗口是`滑动窗口协议`，滑动窗口协议（Sliding Window Protocol），属于 TCP 协议的一种应用，用于网络数据传输时的流量控制，以避免拥塞的发生。 发送方和接收方分别有一个窗口大小 w1 和 w2。窗口大小可能会根据网络流量的变化而有所不同，但是在更简单的实现中它们是固定的。窗口大小必须大于零才能进行任何操作。
+
+我们算法中的滑动窗口也是类似，只不过包括的情况更加广泛。实际上上面的滑动窗口在某一个时刻就是固定窗口大小的滑动窗口，随着网络流量等因素改变窗口大小也会随着改变。接下来我们讲下算法中的滑动窗口。
+
+## 介绍
+
+滑动窗口是一种解决问题的思路和方法，通常用来解决一些连续问题。 比如 LeetCode 的 [209. 长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/209-chang-du-zui-xiao-de-zi-shu-zu-hua-dong-chua-2/)。更多滑动窗口题目见下方`题目列表`。
+
+## 常见套路
+
+滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”，“连续子数组 xxxx”，就应该可以想到滑动窗口。能不能解决另说，但是这种敏感性还是要有的。
+
+从类型上说主要有：
+
+- 固定窗口大小
+- 窗口大小不固定，求解最大的满足条件的窗口
+- 窗口大小不固定，求解最小的满足条件的窗口（上面的 209 题就属于这种）
+
+后面两种我们统称为`可变窗口`。当然不管是哪种类型基本的思路都是一样的，不一样的仅仅是代码细节。
+
+### 固定窗口大小
+
+对于固定窗口，我们只需要固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点，并且保证：
+
+1. l 初始化为 0
+2. 初始化 r，使得 r - l + 1 等于窗口大小
+3. 同时移动 l 和 r
+4. 判断窗口内的连续元素是否满足题目限定的条件
+   - 4.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解
+   - 4.2 如果不满足，则继续。
+
+![](https://tva1.sinaimg.cn/large/00831rSTly1gcw0pwdhmwj308z0d53yt.jpg)
+
+### 可变窗口大小
+
+对于可变窗口，我们同样固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点。后面有所不同，我们需要保证：
+
+1. l 和 r 都初始化为 0
+2. r 指针移动一步
+4. 判断窗口内的连续元素是否满足题目限定的条件
+   - 4.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。循环执行 4.1
+   - 4.2 如果不满足，则继续。
+
+形象地来看的话，就是 r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。
+
+![](https://tva1.sinaimg.cn/large/00831rSTly1gcw0ouuplaj30d90d50t3.jpg)
+
+## 模板代码
+
+以下是 209 题目的代码，使用 Python 编写，大家意会即可。
+
+```python
+class Solution:
+    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
+        l = total = 0
+        ans = len(nums) + 1
+        for r in range(len(nums)):
+            total += nums[r]
+            while total >= s:
+                ans = min(ans, r - l + 1)
+                total -= nums[l]
+                l += 1
+        return  0 if ans == len(nums) + 1 else ans
+```
+
+## 题目列表
+
+以下题目有的信息比较直接，有的题目信息比较隐蔽，需要自己发掘
+
+- [【Python，JavaScript】滑动窗口（3. 无重复字符的最长子串）](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/pythonjavascript-hua-dong-chuang-kou-3-wu-zhong-fu/)
+- [76. 最小覆盖子串](https://leetcode-cn.com/problems/minimum-window-substring/solution/python-hua-dong-chuang-kou-76-zui-xiao-fu-gai-zi-c/)
+- [209. 长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/209-chang-du-zui-xiao-de-zi-shu-zu-hua-dong-chua-2/)
+- [【Python】滑动窗口（438. 找到字符串中所有字母异位词）](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/python-hua-dong-chuang-kou-438-zhao-dao-zi-fu-chua/)
+- [【904. 水果成篮】（Python3）](https://leetcode-cn.com/problems/fruit-into-baskets/solution/904-shui-guo-cheng-lan-python3-by-fe-lucifer/)
+- [【930. 和相同的二元子数组】（Java，Python）](https://leetcode-cn.com/problems/binary-subarrays-with-sum/solution/930-he-xiang-tong-de-er-yuan-zi-shu-zu-javapython-/)
+- [【992. K 个不同整数的子数组】滑动窗口（Python）](https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/992-k-ge-bu-tong-zheng-shu-de-zi-shu-zu-hua-dong-c/)
+- [【1004. 最大连续 1 的个数 III】滑动窗口（Python3）](https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/1004-zui-da-lian-xu-1de-ge-shu-iii-hua-dong-chuang/)
+- [【1234. 替换子串得到平衡字符串】[Java/C++/Python] Sliding Window](https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/javacpython-sliding-window/367697)
+- [【1248. 统计「优美子数组」】滑动窗口（Python）](https://leetcode-cn.com/problems/count-number-of-nice-subarrays/solution/1248-tong-ji-you-mei-zi-shu-zu-hua-dong-chuang-kou/)
+
+## 扩展阅读
+
+- [LeetCode Sliding Window Series Discussion](https://leetcode.com/problems/binary-subarrays-with-sum/discuss/186683/)
