当前位置:网站首页>Well, these four ways to query the maximum value of sliding window are good

Well, these four ways to query the maximum value of sliding window are good

2020-11-09 12:09:56 JAVA Chinese community

This article has been included in Github《 Xiaobai's algorithm 》 series : https://github.com/vipstone/algorithm

This is a basic algorithm problem , The data structure involved is also what we talked about before , I'll buy a pass here first . This interview question has appeared in Amazon's interview in the past six months 28 Time , There has been a byte bounce 7 Time , The data comes from LeetCode.

image.png
Let's first look at the description of the title .

Title Description

Given an array nums And the size of the sliding window k, Please find the maximum value in all sliding windows .

Example :

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

Tips :
You can assume k Always effective , When the input array is not empty ,1 ≤ k ≤  Enter the size of the array .

LeetCode: https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

title

I can't understand the above question ? No problem , Next, take a look at this picture, which can clearly describe the problem :
image.png
As can be seen from the above picture , The meaning of the title is : Given an array , Each query 3 The maximum of the elements , Number 3 For the size of the sliding window , Then move backward in turn to query adjacent 3 The maximum number of elements . The original array in the picture is [1,3,-1,-3,5,3,6,7], The maximum value of the final sliding window is [3,3,5,5,6,7].

After seeing this question , Our first instinct is the brute force solution , Query the maximum value of the sliding window in turn with a two-layer loop , The implementation code is as follows .

Implementation method 1: Violence solution

The implementation idea and code of brute force solution are very intuitive , As shown below :

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //  Judge not empty 
        if (nums == null || k <= 0) return new int[0];
        //  The final result array 
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < res.length; i++) {
            //  Initialize maximum 
            int max = nums[i]; 
            //  loop  k-1  Find the maximum 
            for (int j = i + 1; j < (i + k); j++) {
                max = (nums[j] > max) ? nums[j] : max;
            }
            res[i] = max;
        }
        return res;
    }
}

Submit the above code to LeetCode, The results are as follows :
image.png
As can be seen from the above results , Although the code passed the test , But the execution efficiency is very low , This code can't be used in a production environment , So we need to keep looking for new solutions .

Implementation method 2: Improved version

Let's optimize the above method a little bit , In fact, we don't need to go through two cycles at a time , We just need a layer of loops to get the maximum value of the sliding window ( The maximum value of the previous loop element ), And then when you remove the element , Determine whether the element to be removed is the maximum value of the sliding window , If it is , The second level loop is used to find the maximum value of the new sliding window , Otherwise, just compare the maximum value with the new element , The implementation code is as follows :

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //  Judge not empty 
        if (nums == null || k <= 0) return new int[0];
        //  The final result array 
        int[] res = new int[nums.length - k + 1];
        //  The value removed in the last cycle 
        int r = -Integer.MAX_VALUE; 
        //  Maximum sliding window ( initialization )
        int max = r; 
        for (int i = 0; i < res.length; i++) {
            // 1. Determine the removed value , Whether it is the maximum value of the sliding window 
            if (r == max) {
                // 2. The maximum value of the sliding window is removed , Loop to find the maximum value of the new sliding window 
                max = nums[i]; //  Initialize maximum 
                //  Loop to find the maximum 
                for (int j = i + 1; j < (i + k); j++) {
                    max = Math.max(max, nums[j]);
                }
            } else {
                // 3. Just compare the maximum value of the sliding window with the new increment 
                max = Math.max(max, nums[i + k - 1]);
            }
            //  The final return array record 
            res[i] = max;
            //  Record the elements to be removed in the next round 
            r = nums[i];
        }
        return res;
    }
}

Submit the above code to LeetCode, The results are as follows :
image.png
As can be seen from the above results , After the transformation, the performance has basically met my requirements , At the beginning of that article, we can also use the data structure we have learned before ? What data structure is it talking about ?

In fact, we can use 「 queue 」 To realize this topic , It's also very simple to implement , It's even more convenient than a violent solution , Now let's move on .

Implementation method 3: Priority queue

Another classic solution to this problem , Is to use the way of the largest heap to solve , The structure of the largest heap is as follows :
image.png
The characteristic of the largest heap is that the top of the heap is the largest element in the whole heap .

We can put the value of the sliding window into the maximum heap , This takes advantage of the characteristics of this data structure ( It will put the maximum on top of the heap ), So we can get the maximum value of the sliding window directly , The implementation code is as follows :

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //  Judge not empty 
        if (nums == null || k <= 0) return new int[]{};
        //  The final result array 
        int[] res = new int[nums.length - k + 1];
        //  Priority queue 
        PriorityQueue<Integer> queue = new PriorityQueue(res.length, new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                //  Reverse order ( From big to small , Default is from small to large )
                return i2 - i1;
            }
        });
        //  The first round of element addition 
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }
        res[0] = queue.peek();
        int last = nums[0]; //  Elements to be removed per round 
        for (int i = k; i < nums.length; i++) {
            //  Remove elements outside the sliding window 
            queue.remove(last);
            //  Add a new element 
            queue.offer(nums[i]);
            //  Deposit the maximum value 
            res[i - k + 1] = queue.peek();
            //  Record the elements to be removed in each round ( Slide the left most element of the window )
            last = nums[i - k + 1];
        }
        return res;
    }
}

Code reading

As can be seen from the above code : The biggest pile is Java The corresponding data structure in is the priority queue PriorityQueue, But the default sorting rule of priority queue is from small to large , So we need to create a Comparator  To change the sorting rules ( Sort from big to small ), Then put all the elements of the sliding window into the priority queue , So we can use it directly queue.peek()  I got the maximum value of the sliding window , Then recycle to remove the edge value of the sliding window , So as to solve the problem .

Submit the above code to LeetCode, The results are as follows :
image.png

PS: From the above execution results we can see that , Using priority queues is inefficient , This is because every insert and delete requires the element order of the largest heap to be maintained again , So the efficiency of the whole execution will be very low .

Implementation method 4: deque

Besides the priority queue , We can also use the double ended queue to query the maximum value of the sliding window , Its implementation idea is very similar to that of the maximum heap , But you don't need to maintain the element position every time you add and delete , So it's going to be very efficient .

The core of the realization idea of double ended queue is to always put the maximum value of sliding window at the head of the queue ( That's the far left side of the queue ), The maximum value will be less than the maximum value on the left ( Team leader direction ) Delete all elements of . This is easy to understand , Because these relatively small values are not as large as the maximum , Before the maximum again , That is, their life cycle is shorter than the maximum , So we can delete these relatively small elements directly , As shown in the figure below :

image.png
In this case , So we can put the elements 1 And elements 2 Delete .

The process of double end queue to query the maximum value of sliding window is divided into the following 4 Step :

  1. Remove the leftmost element that is less than the maximum value ( Make sure the maximum value of the sliding window is at the head of the team );
  2. Remove values from the end of the queue that are less than the current value to be added to the queue element ( Eliminate elements with small value and short life cycle );
  3. Add a new element to the end of the queue ;
  4. Add the maximum value to the array of final results .

The implementation code is as follows :

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //  Judge not empty 
        if (nums == null || k <= 0) return new int[0];
        //  The final result array 
        int[] res = new int[nums.length - k + 1];
        //  The stored data is the subscript of the element 
        ArrayDeque<Integer> deque = new ArrayDeque();
        for (int i = 0; i < nums.length; i++) {
            // 1. Remove the subscript beyond the sliding window on the left 
            if (i >= k && (i - k) >= deque.peek()) deque.removeFirst();

            // 2. Remove less than from the back  nums[i]  The elements of 
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
                deque.removeLast();

            // 3. Subscripts join the queue 
            deque.offer(i);

            // 4. Add the maximum value to the array 
            int rindex = i - k + 1;
            if (rindex >= 0) {
                res[rindex] = nums[deque.peek()];
            }
        }
        return res;
    }
}

Submit the above code to LeetCode, The results are as follows :
image.png

As can be seen from the above results , Compared with the priority queue, the double ended queue is , Because there is no need to recalculate and maintain the location of elements , So the execution efficiency is still very high .

summary

In this paper, we use 4 In this way, the function of finding the maximum value of sliding window is realized , The violent solution realizes this function through two layers of circulation , The code is the simplest, but the execution efficiency is not high , And through the maximum heap, that is, the priority queue to achieve ( This topic ) Although it's easier , But the implementation efficiency is not high . So we can choose to use double ended queue or improved code to achieve the maximum value of query sliding window .

Official account 「Java Chinese community 」 See more algorithmic illustrations .

image.png

版权声明
本文为[JAVA Chinese community]所创,转载请带上原文链接,感谢