Leetcode.com/problems/sl…

Discuss:www.cnblogs.com/grandyang/p…

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.

Example 1:

Input: nums = [1, 3, 1, 3,5,3,6,7], k = 3 Output:,3,5,5,6,7 [3] 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 1. [5 3 6] 7 6 1 3-1-3 5 [3 6 7] 7Copy the code

Example 2:

Input: nums = [1], k = 1
Output: [1]
Copy the code

Example 3:

Input: nums = [1,-1], k = 1
Output: [1,-1]
Copy the code

Example 4:

Input: nums = [9,11], k = 2
Output: [11]
Copy the code

Example 5:

Input: nums = [4,-2], k = 2
Output: [4]
Copy the code

Constraints:

  • 1 <= nums.length <= 105

  • -104 <= nums[i] <= 104

  • 1 <= k <= nums.length

Solution a:

We could do this with a priority queue, the maximum heap, but then we put a pair of numbers and their location, and then we know where each number is, and we don’t have to search any more. If the largest number in the priority queue is not in the window at this time, it should be removed. To determine the method, compare the second (position coordinate) in the pair of the first element in the queue with i-k, and remove it if it is less than or equal to. The current number is then paired with its position to join the priority queue. At this point, if I >= k-1, it means that the window size is exactly K, and the maximum value can be added into the result res.

class Solution { fun maxSlidingWindow(nums: IntArray, k: Int): IntArray { val priorityQueue = PriorityQueue<Pair<Int, Int>>(Comparator<Pair<Int, Int>> { o1, o2 -> o2!! .first.compareTo(o1!! .first) }) val result = mutableListOf<Int>() for (index in nums.indices) { while (priorityQueue.isNotEmpty() && priorityQueue.peek().second <= index - k) { priorityQueue.poll() } priorityQueue.offer(Pair(nums[index], index)) if (index >= k - 1) { result.add(priorityQueue.peek().first) } } return result.toIntArray() } }Copy the code

Method 2:

Use a bidirectional queue deque to solve the problem, and remind us to leave only useful values in the window, and remove all useless values. If the first element of the queue is i-k, the window has moved one step to the right and the first element of the queue has been removed. We then compare the end of the queue with the incoming value, remove it if it is small, and then add the first element to the result.

class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        val result = mutableListOf<Int>()

        val deque = ArrayDeque<Int>()

        for (i in nums.indices) {
            if (deque.isNotEmpty() && deque.first == i - k) {
                deque.removeFirst()
            }
            while (deque.isNotEmpty() && nums[deque.last] < nums[i]) {
                deque.removeLast()
            }
            deque.addLast(i)
            if (i >= k - 1) {
                result.add(nums[deque.first])
            }
        }
        return result.toIntArray()
    }
}
Copy the code