力扣 – 劍指 Offer 59 – I. 滑動窗口的最大值

• 2021 年 11 月 9 日
• 筆記
• 單調隊列, 滑動窗口, 演算法與題解, 隊列

題目

劍指 Offer 59 – I. 滑動窗口的最大值

思路1（單調隊列）

• 使用單調（遞減）隊列，保持隊列中的元素是遞減順序，隊列頭保存的是當前窗口中最大的元素
• 首先先模擬建立第一個窗口，同時獲取第一個窗口的最大值（就是隊頭元素）
• 然後每次窗口移動的時候都要判斷移出去的元素是否是最大的元素：將窗口最左邊的元素和隊列頭元素進行比較，如果相等，則需要將隊頭的元素移除，說明窗口的最大值被移出去了，需要尋找新的最大值。而隊列頭的第二個元素是第二大元素，不過還要和即將進入新窗口的那個元素進行比較

程式碼

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;

        if (length == 0 || k == 0) {
            return new int[0];
        }

        // Java內置的雙端隊列
        Deque<Integer> queue = new LinkedList<>();
        int[] res = new int[length - k + 1];

        // 先初始化第一個窗口
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
        }
        // 獲取第一個窗口的最大值
        res[0] = queue.peekFirst();

        // 移動接下來的窗口
        for (int i = k; i < length; i++) {
            // 要判斷窗口右移時，出隊的元素是否是當前最大元素
            if (queue.peekFirst() == nums[i-k]) {
                queue.removeFirst();
            }
            // 保持單調隊列遞減，此時隊首的元素就是當前窗口的最大與阿蘇
            while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
            res[i-k+1] = queue.peekFirst();
        }
        
        return res;

    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(k)\)，單調隊列所佔空間最多為\(O(k)\)，因為隊列最多不會超過窗口的大小