例题

239. 滑动窗口最大值

题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                  最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7


示例 2：

输入：nums = [1], k = 1
输出：[1]

解法

使用双端队列存储当前滑动窗口的元素索引，并且保证它们是从大到小排列，队列的头部始终是当前滑动窗口最大值的索引。

具体步骤如下：

遍历数组nums

1. 如果 deque 不为空且当前元素大于 deque 尾部的元素，则将 deque 尾部的元素移除，直到 deque 为空或当前元素小于等于 deque 尾部的元素。
2. 如果 deque 的头部元素的索引已经不在滑动窗口内（即 i - k >= deque[0]），则从 deque 头部移除该索引。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const deque = []; // 存储索引
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        // 移除不在滑动窗口内的元素索引
        while (deque.length > 0 && deque[0] < i - k + 1) {
            deque.shift();
        }

        // 移除所有比当前元素小的元素索引，它们不可能是最大的
        while (deque.length > 0 && nums[i] > nums[deque[deque.length - 1]]) {
            deque.pop();
        }

        // 将当前元素索引添加到队列中
        deque.push(i);

        // 如果窗口已经形成，则记录当前窗口的最大值
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
};

76. 最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

解法

1. 使用两个哈希表分别记录 t串字符出现次数 和 当前窗口的字符次数
2. 扩展窗口：从字符串 s 的左侧开始，向右侧扩展，直到包含所有的 t串字符
3. 收缩窗口：一旦找到符合条件的窗口，我们就尝试从左侧开始收缩左侧窗口，知道窗口不在满足条件
4. 重复步骤 2 和 3

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    const tCount = {};
    const wCount = {};
    let left = 0;
    let right = 0;
    let minLength = Infinity;
    let minStart = 0;

    // 初始化 t 串的哈希表
    for (let char of t) {
        tCount[char] = (tCount[char] || 0) + 1;
    }

    // 需要匹配的字符种类
    const required = Object.keys(tCount).length;
    // 当前匹配成功的种类数量
    let accept = 0;

    while (right < s.length) {
        // 右侧窗口字符进入窗口
        let char = s[right];
        wCount[char] = (wCount[char] || 0) + 1;

        // 是否能够匹配一个种类
        if (tCount[char] && tCount[char] === wCount[char]) {
            accept ++;
        }

        // 收缩左侧窗口
        while (left <= right && accept === required) {
            // 更新答案
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                minStart = left;
            }

            // 收缩窗口
            const char = s[left];
            wCount[char] --;
            if (tCount[char] && tCount[char] > wCount[char]) {
                accept --;
            }
            left ++;
        }
        right ++;
     }

     return minLength === Infinity ? "" : s.substr(minStart, minLength);
};