什么是滑动窗口?
滑动窗口是一种在数组或字符串上移动一个连续区间、通过增删边界元素来高效处理子区间问题的算法技巧。
滑动窗口可以分为以下三种常见类型，根据窗口是否固定和滑动规则不同：
1. 固定长度滑动窗口（Fixed-size Sliding Window）
特点：
- 窗口大小 k 是固定的
- 每次窗口向右移动一格
适用场景：
- 求长度为 k 的最大/最小值、平均值、和等
举例：你在刷朋友圈，屏幕一次只能显示 3 条动态
你用手机刷朋友圈：
- 屏幕一次能显示 3 条
- 你每次往上滑一格，就看到下一组连续的 3 条动态
- 你在找：哪一组 3 条朋友圈点赞数最多？
对应题目：
就像窗口每次只看 3 条内容，滑一下换一个人进来，一个人滑出去 —— 窗口大小始终固定
2. 可变长度滑动窗口（Variable-size Sliding Window）
特点：
- 窗口大小不固定，依据条件动态扩展或收缩
- 常用于处理满足某种条件的最短/最长子数组、子串
适用场景：
- 最短包含所有字符的子串
- 最长不含重复字符的子串
举例：手机登录检测——找出最长连续没有重复设备登录的时间段
你是平台安全负责人，想找出某用户最“稳定”的登录时段 —— 这段时间内没有使用两个重复设备登录。
- 每次用户登录，我们记录设备 ID
- 一旦设备重复了，说明“安全区间”结束，需要缩小窗口
- 然后你继续往后检查，直到找出最长那段不重复设备登录时间
对应题目：
我们就像在找一段最长的“干净登录记录”窗口，没有重复设备号
3. 双端滑动窗口（Two-end or Deque-based Sliding Window）
特点：
- 使用 双端队列（deque） 来维护窗口内的最大值、最小值等信息
- 保持窗口内元素的某种“单调性”（比如递减）
适用场景：
- 在 O(n) 时间内找出每个窗口的最大值/最小值
- 比较高级，用队列代替常规数组处理窗口值
思路简要：
- 用队列保存窗口中“有可能成为最大值的候选项”
- 每滑动一格，弹出不可能成为最大值的元素，保持队列递减
举例：股市滑动分析——每 3 天内找出股价最高点
你是股市分析师，要每天告诉客户：“过去 3 天内的最高股价是多少”。
- 你维护一个“候选名单”（队列），里面只保留可能是最大值的价格
- 每次股价变化，滑动窗口，你踢出旧的股价，引入新的
- 队列始终从大到小排，队首就是当前窗口的最大值
对应题目：
就像你每天更新“最近3天最高股价”，只保留可能变成最大值的记录