木易

# 滑动窗口

# 算法思路

  1. 使用双指针中的左右指针技巧，初始化left = right = 0，把区间 [left, right)称为一个「窗口」。
  2. 先不断地增加 right 指针扩大窗口[left, right)，直到窗口符合要求
  3. 停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口不再符合要求。同时，每次增加 left，我们都要更新一轮结果。
  4. 重复第 2 和第 3 步，直到 right 到达尽头。 第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。 左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

# 应用场景

  • 滑动窗口适用的题目一般具有单调性
  • 滑动窗口、双指针、单调队列和单调栈经常配合使用

# 代码模板

int left = 0, right = 0;    // 左右指针
while (right < s.size()) {  // 右指针遍历直到边界
    window.add(s[right]);   // 右元素进窗
    right++;                // 右指针移动

    while ( left < right && valid(window)) {    // 窗口满足条件(优化窗口)
        window.remove(s[left]); // 左元素出窗
        left++;                 // 左指针移动；直到窗口不满足条件
    }
}
1
2
3
4
5
6
7
8
9
10

# 例题

# 209. 长度最小的子数组 (opens new window)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, r = 0, sum = 0, ans = Integer.MAX_VALUE;
        while (r < nums.length){
            sum+= nums[r++];
            while (l <r && sum >= target) {
                ans= Math.min(ans, r-l);
                sum-= nums[l++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0: ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 187. 重复的 DNA 序列 (opens new window)

滑动窗口

  • 条件：长度为 10

  • 窗口记录：StringBuilder 保存窗口子串 集合：

  • 记录已经出现的子串

# 239. 滑动窗口最大值 (opens new window)

滑动窗口+单调双端队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int l = 0, r = 0;
        int n = nums.length;
        int[] res = new int[n - k + 1];
        while (r < n) {
            while (!deque.isEmpty() && nums[r] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(r++);
            while (!deque.isEmpty() && deque.getFirst() < r - k) deque.removeFirst();
            if (r >= k) res[r-k] = nums[deque.getFirst()];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 220. 存在重复元素 III (opens new window)

滑动窗口+红黑树

其他练习题目

← 0x42_单调栈 →