239.sliding-window-maximium.md

239. Sliding Window Maximum

Monotonic Queue

假設之前窗口是這樣 [7, 1, 3] 然後現在要加入 5，那表示未來的 k 個窗口，[3, 1] 都不會是最大值，所以我們可以把他們移除，剩下 [7, 5]

k = 3
[7, 1, 3] 5
            * // new added
   [1, 3, 5]
       [3, 5, X]
           [5, X, X]

而 [7, 5] 代表的是 7 只要還在窗口內，那麼他就會是滑窗的最大值，直到 7 也跑出窗口之外，我們就需要移掉 7。

核心思路就是我們使用一個單調遞減 (由大到小) 的雙端隊列，來維護目前滑窗可能的最大值索引。

1. 每當有新元素加入，就將隊列尾端較小的元素移除，直到隊列尾端元素比新元素大。因為他們不可能是未來的最大值。
2. 將新元素加到隊列尾端。
3. 這時候隊列的第一個元素都是當前窗口的最大值位置。所以我們可以用 O(1) 來取得當前滑窗的最大值。
4. 如何知道目前最大值已經不在窗口內了？當該目前最大值的索引超出當前滑動窗口（即 i - k），則將其從隊列首端移除。

為何使用雙端隊列？

• 隊列第一個元素都是目前滑窗的最大值。
• 對列尾端負責維持遞減序列，用來清除未來不可能成為最大值的元素。

fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
    val result = mutableListOf<Int>()
    val deque = ArrayDeque<Int>() // Stores indices of elements in decreasing order

    for (i in nums.indices) {
        // Remove elements outside the window
        /**
         * A, B, C, D, E
         *          i
         * X  |--k--|
         * Remove!
         */
        if (deque.isNotEmpty() && deque.first() <= i - k) {
            deque.removeFirst()
        }

        // Remove elements smaller than current element (from back)
        while (deque.isNotEmpty() && nums[deque.last()] < nums[i]) {
            deque.removeLast()
        }

        // Add current index
        deque.addLast(i)

        // Add max to result (only when window is full, like fixed-size sliding window)
        if (i >= k - 1) {
            result.add(nums[deque.first()])
        }
    }
    return result.toIntArray()
}

Sorted Set

We can maintain a fixed-size sorted set to represent the window, and we can use the first element to represent the maximum value.

fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
    val n = nums.size
    val results = IntArray(n - k + 1)
    val treeSet = TreeSet<Int>() { i1, i2 ->
        nums[i2] - nums[i1]
    }
    for (i in nums.indices) {
        treeSet.add(i)
        if (i >= k) {
            treeSet.remove(i - k)
        }
        if (i >= k - 1) {
            results.add(nums[treeSet.first()])
        }
    }
    return results
}

• Time Complexity: O(n lg k).
• Space Complexity: O(k) for sorted set.