Stack and queue - 239. Sliding window maximum

1 Title Description

Give you an array of integers nums, There is a size of k The sliding window of the array moves from the leftmost side to the rightmost side of the array . You can only see... In the sliding window k A digital . The sliding window moves only one bit to the right at a time .

return The maximum value in the sliding window .

2 Title Example

Example 2：

Input ：nums = [1], k = 1
Output ：[1]

3 Topic tips

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

4 Ideas

queue ：
about 「 Maximum 」, We can think of — A very suitable data structure , That's the priority queue ( Pile up ), The large root heap can help us maintain in real time — Maximum value in series elements .
For this question , At the beginning , We will array nums Before k Put elements in the priority queue . Whenever we move the window to the right , We can put a new element in the priority queue , At this time, the element at the top of the heap is the maximum value of all elements in the heap . However, this maximum may not be in the sliding window , under these circumstances , This value is in the array nums The position in appears to the left of the left boundary of the sliding window . therefore , When we continue to move the window to the right , This value will never appear in the sliding window , We can permanently remove it from the priority queue . We constantly remove elements from the top of the heap , Until it does appear in the sliding window . here , The top element is the maximum value in the sliding window . In order to judge the position relationship between the heap top element and the sliding window , We can store two tuples in the priority queue (num, indez), Show elements num The subscript in the array is indez.

Complexity analysis
Time complexity :O(n log n), among n It's an array nums The length of . In the worst case , Array nums The elements in are monotonically increasing , Then the final priority queue contains all the elements , No elements have been removed . Because the time complexity of putting an element into the priority queue is O(log n), So the total time complexity is O(n logn).
Spatial complexity :O(n), That is, the space needed by the priority queue . All spatial complexity analyses here do not consider the need for the returned answer O(n) Space , Only calculate the use of additional space .

5 My answer

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
    
            public int compare(int[] pair1, int[] pair2) {
    
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
    
            pq.offer(new int[]{
    nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
    
            pq.offer(new int[]{
    nums[i], i});
            while (pq.peek()[1] <= i - k) {
    
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}