題目描述：給定一個(gè)數(shù)組 nums 和滑動(dòng)窗口的大小 k，請找出所有滑動(dòng)窗口里的最大值。

示例：

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7] 
解釋: 

  滑動(dòng)窗口的位置                最大值
---------------               -----
[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

解法 1：暴力法

這題其實(shí)暴力法時(shí)間效率也很高，直接移動(dòng)這個(gè)滑動(dòng)窗口，每次統(tǒng)計(jì)窗口中的最大值即可。

代碼實(shí)現(xiàn)：

// ac地址：https://leetcode-cn.com/problems/sliding-window-maximum/
// 原文地址：https://xxoo521.com/2020-03-27-max-sliding-window/
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    if (k <= 1) return nums;
    const res = [];
    for (let i = 0; i < nums.length - k + 1; ++i) {
        res.push(Math.max(...nums.slice(i, i + k)));
    }
    return res;
};

時(shí)間復(fù)雜度是，其中 k 是滑動(dòng)窗口的長度。空間復(fù)雜度是。

解法 2: 動(dòng)態(tài)規(guī)劃

官方題解中講的很清楚了。

這里簡單說下重要的點(diǎn)：將數(shù)組分成大小相等的塊，每個(gè)塊都可以理解為有兩個(gè)數(shù)組 left 和 right。left 方向從左到右，right 相反。left[i]是指塊從開始到下標(biāo) i 的最大元素，right[j]是指塊從開始到下標(biāo) j 的最大元素。

假設(shè)滑動(dòng)窗口的范圍是[i, j]，很容易看出來，滑動(dòng)窗口中的最大值就是 max(right[i], left[j])。

代碼實(shí)現(xiàn)如下：

// ac地址：https://leetcode-cn.com/problems/sliding-window-maximum/
// 原文地址：https://xxoo521.com/2020-03-27-max-sliding-window/
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    if (k === 1) return nums;
    const length = nums.length;
    if (!length) return [];

    const left = new Array(length);
    const right = new Array(length);

    left[0] = nums[0];
    right[length - 1] = nums[length - 1];
    for (let i = 1; i < length; ++i) {
        if (i % k) {
            left[i] = Math.max(nums[i], left[i - 1]);
        } else {
            left[i] = nums[i];
        }

        let j = length - i - 1;
        if ((j + 1) % k) {
            right[j] = Math.max(nums[j], right[j + 1]);
        } else {
            right[j] = nums[j];
        }
    }

    const res = [];
    for (let i = 0; i < length - k + 1; i++) {
        res.push(Math.max(right[i], left[i + k - 1]));
    }
    return res;
};

這種做法時(shí)間復(fù)雜度比解法 1 更低，是。

解法 3: 雙端隊(duì)列

官方用動(dòng)畫演示了算法過程。

這里記錄下重要的點(diǎn)：

• 雙端隊(duì)列中保存的是元素下標(biāo)，方便判斷元素是否在當(dāng)前滑動(dòng)窗口中
• 雙端隊(duì)列頭元素對應(yīng)的數(shù)字，就是當(dāng)前滑動(dòng)窗口的最大值
• 雙端隊(duì)列頭尾出入元素的時(shí)間復(fù)雜度是
• 本題的雙端隊(duì)列用到功能，用鏈表就可以滿足。C++的 STL 中的雙端隊(duì)列支持 insert，考慮了拷貝的高效型，實(shí)現(xiàn)上更復(fù)雜

為了方便，代碼使用數(shù)組來模擬雙端隊(duì)列。代碼實(shí)現(xiàn)如下：

// ac地址：https://leetcode-cn.com/problems/sliding-window-maximum/
// 原文地址：https://xxoo521.com/2020-03-27-max-sliding-window/
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    if (k === 0) return [];
    const length = nums.length;
    if (length === 0) return [];

    const deque = [];
    for (let i = 0; i < k; ++i) {
        cleanDeque(deque, nums, i, k);
        deque.push(i);
    }

    const res = [];
    res.push(nums[deque[0]]);

    for (let i = k; i < length; ++i) {
        cleanDeque(deque, nums, i, k);
        deque.push(i);
        res.push(nums[deque[0]]);
    }

    return res;
};

/**
 * 刷新雙端隊(duì)列
 * @param {number[]} queue 雙端隊(duì)列
 * @param {number[]} nums 數(shù)組
 * @param {number} idx 當(dāng)前元素下標(biāo)
 * @param {number} k 滑動(dòng)窗口大小
 */
function cleanDeque(queue, nums, idx, k) {
    // 如果雙向隊(duì)列中，包含不是滑動(dòng)窗口內(nèi)的數(shù)，直接出隊(duì)
    if (queue.length && idx >= k + queue[0]) {
        queue.shift();
    }

    while (queue.length && nums[idx] > nums[queue[queue.length - 1]]) {
        queue.pop();
    }
}

由于每個(gè)元素只有 1 次機(jī)會進(jìn)出雙端隊(duì)列，所以時(shí)間復(fù)雜度是。

更多資料

整理不易，若對您有幫助，請給個(gè)「關(guān)注+點(diǎn)贊」，您的支持是我更新的動(dòng)力 ??

• ??Blog：劍指 Offer 題解 + JS 代碼
• ??Github ：https://github.com/dongyuanxin/blog
• ?? 公眾號：心譚博客