239. Maximum value of sliding window (difficult) - one-way queue, large top heap - byte skipping high frequency problem

One 、 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 .

Example 1：

 Input ：nums = [1,3,-1,-3,5,3,6,7], k = 3
 Output ：[3,3,5,5,6,7]
 explain ：
 Position of sliding window                  Maximum 
---------------               -----
[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]

Two 、 Problem solving

One way queue

First of all, this question needs to pay attention to two points

• Maintain the sliding window length value , The sliding window value is k;
• Maintain one-way queue and save subscript value , Left and right Subscripts ,[ Zuo Da , The lower right ], The subscript value on the left represents the largest value , The smallest on the right , Make the elements in the queue from large to small .

When the current value is greater than the end value in the one-way queue , Delete tail value , Save the element values of the one-way queue in descending order , If the interval value of the left and right subscripts exceeds the sliding window value , The left boundary is updated .

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        int length = nums.length;
        // The queue holds subscript values , The interval of subscript value to maintain the size and length of sliding window 
        Deque<Integer> queue =  new LinkedList<>();
        // Initialize sliding window 
        for(int i = 0;i<k;i++){
    
            // Ensure that the subscript of the sliding window [ Zuo Da , Right small ]. The current value is greater than the end of line element   Then update the maximum value 
            while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]){
    
                queue.pollLast();
            }
            // Add elements to the end of the team 
            queue.addLast(i);
        }
        int[] res = new int[length - k + 1];
        res[0] = nums[queue.peekFirst()];
        for(int i = k;i<length;i++){
    
            // If the current value is greater than the end of line element , Then go straight out of the team ,
            while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]){
    
                queue.pollLast();
            }
            // Save the current subscript at the end of the queue 
            queue.addLast(i);
            // Maintain the size of the sliding window 
            while(queue.peekFirst() <= i - k){
    
                queue.pollFirst();
            }
            res[i-k+1] = nums[queue.peekFirst()];
        }
        return res;
    }
}

Big pile top

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        // Big pile top 
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>(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;
    }
}