Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Approach

Monotonic Stack

1. Create a stack that maintains the elements in decreasing order
2. Remove all elements that are out of the window
3. If we get a larger element in the current index, we won't be using the previous smaller elements in the next windows so remove them from stack.
4. Add the current element to stack.

fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
    val res = IntArray(nums.size - k + 1)
    val stack = ArrayDeque<Int>()

    for(i in 0 until nums.size) {

        // remove elements that are out of the window
        while(stack.isNotEmpty() && stack.first() <= i - k) stack.removeFirst()

        // remove elements smaller than the current as they won't be useful
        while(stack.isNotEmpty() && nums[i] > nums[stack.last()]) stack.removeLast()

        stack.add(i)

        if(i >= k-1) res[i - k + 1] = nums[stack.first()]
    }

    return res
}