This article has been included in Github “Xiaobai Algorithms” series: github.com/vipstone/al…

This is a fairly basic algorithm problem, and it involves the same data structure that we talked about before, so I’m going to buy a trick here. This question has been asked 28 times in amazon interviews and seven times in ByteDance in the last six months, according to LeetCode.

Let’s start with the description of the problem.

Topic describes

Given an array nums and the size k of the sliding window, find the maximum number of sliding Windows.

Example:

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

Tip: You can assume that k is always valid, in the case that the input array is not empty, 1 ≤ k ≤ the size of the input array.

LeetCode:leetcode-cn.com/problems/hu…

title

Don’t understand the above questions? That’s okay. Here’s a picture that clearly illustrates the problem:Given an array, query the maximum value of three elements at a time. The number 3 is the size of the sliding window, and then move backward in turn to query the maximum value of the three adjacent elements. The original array in the image is[1, 3, 1, 3,5,3,6,7], the maximum value of the final sliding window is,3,5,5,6,7 [3].

After seeing this problem, our first intuition is the violent solution, using a two-layer cycle to query the maximum value of the sliding window, the implementation code is as follows.

Implementation method 1: violent solution

The implementation idea and implementation code of the violent solution is very intuitive, as shown below:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // Non-null judgment
        if (nums == null || k <= 0) return new int[0];
        // Final result array
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < res.length; i++) {
            // Initialize the maximum value
            int max = nums[i]; 
            // loop k-1 times to find the maximum value
            for (int j = i + 1; j < (i + k); j++) {
                max = (nums[j] > max) ? nums[j] : max;
            }
            res[i] = max;
        }
        returnres; }}Copy the code

Submit the above code to LeetCode and execute as follows:As we can see from the above results, although the code passed the test, it was poorly executed and was not suitable for production, so we needed to continue to look for new solutions.

Implementation method 2: improved version

Then we optimize a little bit about the above methods, actually we don’t need every time after two layer circulation, we only need to get the maximum sliding window layer cycle (the maximum cycle elements before), and then remove elements, judge whether the elements of the current to remove for a maximum of sliding window, if it is, The second layer of loop is used to find the maximum value of the new sliding window. Otherwise, it is only necessary to compare the maximum value with the new element. The code is as follows:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // Non-null judgment
        if (nums == null || k <= 0) return new int[0];
        // Final result array
        int[] res = new int[nums.length - k + 1];
        // The value removed from the previous loop
        int r = -Integer.MAX_VALUE; 
        // Sliding window maximum (initialization)
        int max = r; 
        for (int i = 0; i < res.length; i++) {
            // 1. Check whether the value to be removed is the maximum value of the sliding window
            if (r == max) {
                // 2. Remove the maximum value of the sliding window and loop to find the new maximum value of the sliding window
                max = nums[i]; // Initialize the maximum value
                // 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 value
                max = Math.max(max, nums[i + k - 1]);
            }
            // Finally returns the array record
            res[i] = max;
            // Record the elements to be removed from the round
            r = nums[i];
        }
        returnres; }}Copy the code

Submit the above code to LeetCode and execute as follows:It can be seen from the above results that the performance of the transformation has basically met my requirements. Then, it was mentioned at the beginning of the article that the data structure we learned before can be used in this problem? What data structure is it talking about?

In fact, we can implement this problem by using “queue”, which is also very simple, even more convenient than the violent solution, so let’s move on.

Implementation method 3: priority queue

Another classic way to solve this problem is to use the largest heap, which is structured as follows: The property of the largest heap is that the top of the heap is the largest element in the heap.

We can put the value of the sliding window into the maximum heap, which takes advantage of the data structure (it puts the maximum value on the top of the heap), so we can get the maximum value of the sliding window directly, as follows:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // Non-null judgment
        if (nums == null || k <= 0) return new int[] {};// 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) {
                // In reverse order (from largest to smallest, default is from smallest to largest)
                returni2 - i1; }});// The first round of element additions
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }
        res[0] = queue.peek();
        int last = nums[0]; // The element to be removed in each 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]);
            // Store the maximum value
            res[i - k + 1] = queue.peek();
            // Record the element to be removed in each round (the element at the left of the slide window)
            last = nums[i - k + 1];
        }
        returnres; }}Copy the code

Code reading

As you can see from the above code: PriorityQueue Is a Java data structure that sorts from smallest to largest by default, so we need to create a Comparator to change the sorting rules. We then put all elements of the sliding window into the priority queue, so we can use queue.peek() directly to get the maximum sliding window value, and then loop to remove the sliding window edge value, thus solving the problem.

Submit the above code to LeetCode and execute as follows:

PS: From the above results, we can see that the execution efficiency of using priority queue is very low. This is because each insertion and deletion needs to re-maintain the order of the largest heap of elements, so the overall execution efficiency is very low.

Implementation method 4: double – ended queue

In addition to the priority queue, we can also use a double-ended queue to query the maximum number of sliding Windows, which is similar to the implementation of the maximum heap, but does not require the maintenance of the element position every time it is added and removed, so it can be very efficient.

The core of the idea is to always place the maximum value of the sliding window at the top of the queue (that is, the leftmost part of the queue), and delete all elements less than the maximum value and to the left of the maximum value (the direction of the head of the queue). This also makes sense, because these relatively small values are not as large as the maximum value, but before the maximum value, that is, their lifetime is shorter than the maximum value, so we can directly delete these relatively small elements, as shown in the following figure:

In this case, we can delete elements 1 and 2.

The process of querying the maximum sliding window value in a dual-end queue is divided into the following four steps:

  1. Remove the leftmost element that is less than the maximum value (ensure that the maximum value of the sliding window is at the top of the queue);
  2. Removes values smaller than those currently added to the queue from the end of the queue (eliminating elements with small values and short life cycles);
  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) {
        // Non-null judgment
        if (nums == null || k <= 0) return new int[0];
        // 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 left subscript that exceeds the slider window
            if (i >= k && (i - k) >= deque.peek()) deque.removeFirst();

            // 2. Remove elements less than nums[I] from the back
            while(! deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.removeLast();// 3. The subscript is queued
            deque.offer(i);

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

Submit the above code to LeetCode and execute as follows:

From the above results, it can be seen that compared to the priority queue, the two-ended queue is relatively efficient because there is no need to recalculate and maintain the position of the element.

conclusion

In this paper, we have realized the function of finding the maximum value of the sliding window in four ways. Among them, the brute force solution realizes this function through a two-layer cycle. The code is the simplest but the execution efficiency is not high, while the maximum heap is the priority queue (in this case) although it is more convenient, but the execution efficiency is not high. So we can choose to use a double-endian queue or a modified version of the code to maximize the query sliding window.

Follow the public account “Java Chinese Community” to see more examples of algorithms.