239. Sliding Window Maximum

Hard
Description

給定一個整數陣列 nums 和一個整數 k（視窗大小），視窗從左向右滑動，每次移動一格。回傳每個視窗位置的最大值。

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7]

Intuition#

用單調遞減的雙端佇列（Deque）維護視窗內的「候選最大值」，佇列頭部永遠是當前最大值。

  • 暴力法每個視窗都要 O(k) 找最大值，太慢
  • 維護一個單調遞減的 Deque，存放元素的索引
  • 新元素進入時，從尾部移除所有比它小的元素（因為它們不可能再成為最大值）
  • 頭部元素超出視窗範圍時從頭部移除

Approaches#

1: Brute Force#

  • 概念: 對每個視窗位置，遍歷視窗內所有元素找最大值
  • 時間複雜度: O(n * k)
  • 空間複雜度: O(1)（不含輸出）
Brute Force 程式碼
class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        val result = IntArray(nums.size - k + 1)
        for (i in result.indices) {
            var max = nums[i]
            for (j in i until i + k) {
                max = maxOf(max, nums[j])
            }
            result[i] = max
        }
        return result
    }
}

⭐2: Monotonic Deque#

  • 概念: 維護一個單調遞減的雙端佇列，佇列頭部即為當前視窗最大值
  • 時間複雜度: O(n)，每個元素最多入隊出隊各一次
  • 空間複雜度: O(k)
class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        val result = IntArray(nums.size - k + 1)
        val deque = ArrayDeque<Int>() // 存索引
        for (right in nums.indices) {
            // 移除尾部所有比當前元素小的
            while (deque.isNotEmpty() && nums[deque.last()] <= nums[right]) {
                deque.removeLast()
            }
            deque.addLast(right)
            // 移除超出視窗的頭部元素
            if (deque.first() < right - k + 1) {
                deque.removeFirst()
            }
            // 視窗形成後記錄結果
            if (right >= k - 1) {
                result[right - k + 1] = nums[deque.first()]
            }
        }
        return result
    }
}

Deque 中存的是索引而非值，這樣才能判斷頭部元素是否超出視窗範圍。比較大小時用 nums[deque.last()] 取值。

🔑 Takeaways#

  • Pattern: 單調 Deque（Monotonic Deque）
  • 關鍵技巧: 單調 Deque 是解決「滑動視窗中的最值」問題的標準工具。核心思想：如果一個元素比後來的元素小且位置更靠前，它永遠不可能成為答案，可以安全移除