239.sliding-window-maximium.md

239. Sliding Window Maximum

Monotonic Queue

• 假設之前窗口是這樣 [7, -1, -3] 然後現在要加入 5，那表示未來的幾個窗口，[-3, -1] 都不會是最大值，所以我們可以把他們移除，剩下 [7, 5]，直到 7 也跑出窗口之外了，那麼移掉 7 而 5 就是目前的最大值。這表示我們要維護一個單調遞減的雙端隊列，要尋找下一個更大值。

那麼我們怎麼知道目前窗口的最大值呢？這個隊列的第一個元素就會是的最大值

當目前位置減掉隊列第一個元素位置 > 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
        if (deque.isNotEmpty() && deque.first() < i - k + 1) {
            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)
        if (i >= k - 1) {
            result.add(nums[deque.first()])
        }
    }

    return result.toIntArray()
}

Heap

TODO:

fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
    val results = IntArray(nums.size - k + 1)
    var resultIndex = 0
    var start = 0
    var end = 0
    val maxHeap = PriorityQueue<Int>() { index1, index2 -> nums[index2] - nums[index1] }   
    
    val passed = hashSetOf<Int>()
    while (end < nums.size) {
        maxHeap.add(end)
        while (end - start + 1 > k) {
            // When we shrink the window, the item still in heap, and we 
            // can't remove from the heap directly, so we add to hash table.
            passed.add(start)
            start++
        }
        
        if (end - start + 1 == k) {
            var maxIndex = maxHeap.poll()
            // We skip the item that is out of the window
            while (passed.contains(maxIndex)) {
                maxIndex = maxHeap.poll()
            }
            results[resultIndex] = nums[maxIndex]
            maxHeap.add(maxIndex)
            resultIndex++
        }
        end++
    }
    return results
}

• Time Complexity: O(n lg n).
• Space Complexity: O(n) for heap and hash table.