[LeetCode][Kotlin] 239. Sliding Window Maximum

239. 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.

정수 nums 배열이 주어지고, 배열의 가장 왼쪽에서 가장 오른쪽으로 이동하는 k 크기의 슬라이딩 윈도우가 있습니다. 윈도우에서 k개의 숫자만 볼 수 있습니다. 슬라이딩 윈도우가 오른쪽으로 한 위치씩 이동할 때마다.

최대 슬라이딩 윈도우를 반환합니다.

 

Example 1:

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

Output: [3,3,5,5,6,7]

Explanation: 

Window position                Max

---------------               -----

[1  3  -1] -3  5  3  6  7       3

 1 [3  -1  -3] 5  3  6  7       3

 1  3 [-1  -3  5] 3  6  7       5

 1  3  -1 [-3  5  3] 6  7       5

 1  3  -1  -3 [5  3  6] 7       6

 1  3  -1  -3  5 [3  6  7]      7

 

Example 2:

Input: nums = [1], k = 1

Output: [1]

 

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

---

코드

class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        val output = mutableListOf<Int>()
        val q = ArrayDeque<Int>()
        var l = 0
        var r = 0

        while (r < nums.size) {
            while (q.isNotEmpty() && nums[q.last()] < nums[r]) {
                q.removeLast()
            }
            q.add(r)

            if (l > q.first()) {
                q.removeFirst() // nums=[1,-1], k=1
            }

            if (r + 1 >= k) {
                output.add(nums[q.first()])
                l++
            }
            r++
        }

        return output.toIntArray()
    }
}