JavaScript滑動窗口的最大值問題怎么解決

JavaScript滑動窗口的最大值問題怎么解決

滑動窗口的最大值問題是一個經典的算法問題，廣泛應用于數據處理、圖像處理、實時監控等領域。本文將詳細介紹如何使用JavaScript解決滑動窗口的最大值問題，包括問題描述、算法思路、代碼實現以及優化方法。

問題描述

給定一個整數數組 nums 和一個整數 k，其中 k 是滑動窗口的大小?；瑒哟翱趶臄到M的最左端移動到最右端，每次移動一個位置。要求返回每個滑動窗口中的最大值。

例如：

輸入: 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

算法思路

暴力法

最直觀的方法是使用暴力法，即對于每個滑動窗口，遍歷窗口中的所有元素，找到最大值。這種方法的時間復雜度為 O(n*k)，其中 n 是數組的長度，k 是窗口的大小。雖然這種方法簡單易懂，但在處理大規模數據時效率較低。

雙端隊列法

為了提高效率，我們可以使用雙端隊列（Deque）來優化算法。雙端隊列是一種具有隊列和棧性質的數據結構，可以在隊列的兩端進行插入和刪除操作。

具體思路如下：

1. 初始化一個空的雙端隊列 deque 和一個結果數組 result。
2. 遍歷數組 nums，對于每個元素 nums[i]：
   • 如果隊列不為空且隊列的頭部元素已經不在當前窗口內（即 deque[0] < i - k + 1），則將其從隊列中移除。
   • 如果隊列不為空且隊列的尾部元素小于當前元素 nums[i]，則將其從隊列中移除，直到隊列為空或隊列的尾部元素大于等于當前元素。
   • 將當前元素的索引 i 添加到隊列的尾部。
   • 如果當前窗口已經形成（即 i >= k - 1），則將隊列的頭部元素對應的值 nums[deque[0]] 添加到結果數組 result 中。
3. 返回結果數組 result。

這種方法的時間復雜度為 O(n)，因為每個元素最多只會被插入和刪除一次。

代碼實現

以下是使用雙端隊列法解決滑動窗口最大值問題的JavaScript代碼實現：

function maxSlidingWindow(nums, k) {
    if (nums.length === 0 || k === 0) return [];
    
    const deque = []; // 雙端隊列，存儲元素的索引
    const result = []; // 結果數組
    
    for (let i = 0; i < nums.length; i++) {
        // 移除不在當前窗口內的元素
        if (deque.length > 0 && deque[0] < i - k + 1) {
            deque.shift();
        }
        
        // 移除隊列中所有小于當前元素的元素
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
        
        // 將當前元素的索引添加到隊列尾部
        deque.push(i);
        
        // 如果窗口已經形成，將隊列頭部元素對應的值添加到結果數組
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    
    return result;
}

// 示例
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindow(nums, k)); // 輸出: [3, 3, 5, 5, 6, 7]

優化方法

雖然雙端隊列法已經將時間復雜度優化到了 O(n)，但在實際應用中，我們還可以進一步優化空間復雜度。具體來說，我們可以使用一個變量來記錄當前窗口的最大值，而不是使用雙端隊列。

優化思路

1. 初始化一個變量 max 來記錄當前窗口的最大值。
2. 遍歷數組 nums，對于每個元素 nums[i]：
   • 如果當前窗口已經形成（即 i >= k - 1），則將 max 添加到結果數組 result 中。
   • 如果當前元素 nums[i] 大于 max，則更新 max 為 nums[i]。
   • 如果當前窗口的最大值 max 已經不在當前窗口內（即 max === nums[i - k]），則重新計算當前窗口的最大值。
3. 返回結果數組 result。

這種方法的時間復雜度仍為 O(n)，但空間復雜度降低到了 O(1)。

優化代碼實現

以下是使用優化方法解決滑動窗口最大值問題的JavaScript代碼實現：

function maxSlidingWindow(nums, k) {
    if (nums.length === 0 || k === 0) return [];
    
    let max = -Infinity; // 當前窗口的最大值
    const result = []; // 結果數組
    
    for (let i = 0; i < nums.length; i++) {
        if (i >= k - 1) {
            // 如果當前窗口已經形成，將最大值添加到結果數組
            result.push(max);
        }
        
        // 更新當前窗口的最大值
        if (nums[i] > max) {
            max = nums[i];
        }
        
        // 如果當前窗口的最大值已經不在窗口內，重新計算最大值
        if (i >= k - 1 && max === nums[i - k + 1]) {
            max = -Infinity;
            for (let j = i - k + 2; j <= i; j++) {
                if (nums[j] > max) {
                    max = nums[j];
                }
            }
        }
    }
    
    return result;
}

// 示例
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindow(nums, k)); // 輸出: [3, 3, 5, 5, 6, 7]

總結

滑動窗口的最大值問題是一個經典的算法問題，可以通過暴力法、雙端隊列法和優化方法來解決。其中，雙端隊列法的時間復雜度為 O(n)，空間復雜度為 O(k)，而優化方法的時間復雜度仍為 O(n)，但空間復雜度降低到了 O(1)。在實際應用中，我們可以根據具體需求選擇合適的算法來解決滑動窗口的最大值問題。

通過本文的介紹，相信讀者已經掌握了如何使用JavaScript解決滑動窗口的最大值問題。希望本文能對讀者在實際開發中遇到的類似問題提供幫助。