Well, these four methods for querying the maximum value of sliding window are good

This is a relatively 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 28 times in Amazon's interview in the last half year and 7 times in byte beating. The data comes from leetcode.

Title Description

Given an array num and the size k of the sliding window, please find the maximum value in all sliding windows.

Example:

Tip: you can assume that K is always valid. When the input array is not empty, 1 ≤ K ≤ the size of the input array.

Topic analysis

Can't you understand the above title? It doesn't matter. Next, look at this picture to clearly describe the problem:

After seeing this problem, our first intuition is the violent solution. We use two-layer loops to query the maximum value of the sliding window in turn. The implementation code is as follows.

Implementation method 1: violence solution

The implementation idea and code of violence solution are very intuitive, as shown below:

class Solution {
    public int[] maxSlidingWindow(int[] nums,int k) {
        // 非空判断
        if (nums == null || k <= 0) return new int[0];
        // 最终结果数组
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < res.length; i++) {
            // 初始化最大值
            int max = nums[i]; 
            // 循环 k-1 次找最大值
            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, and the execution results are as follows:

Implementation method 2: improved version

Next, let's slightly optimize the above method. In fact, we don't need to go through two layers of loops every time, We only need one layer of loop to get the maximum value of the sliding window (the maximum value of the previous cyclic element), and then when removing the element, judge whether the element currently to be removed is the maximum value of the sliding window. If so, carry out the second level cycle to find the maximum value of the new sliding window. Otherwise, you only need to compare the maximum value with the newly added element. The implementation code is as follows:

class Solution {
    public int[] maxSlidingWindow(int[] nums,int k) {
        // 非空判断
        if (nums == null || k <= 0) return new int[0];
        // 最终结果数组
        int[] res = new int[nums.length - k + 1];
        // 上一轮循环移除的值
        int r = -Integer.MAX_VALUE; 
        // 滑动窗口最大值（初始化）
        int max = r; 
        for (int i = 0; i < res.length; i++) {
            // 1.判断移除的值，是否为滑动窗口的最大值
            if (r == max) {
                // 2.移除的是滑动窗口的最大值，循环找到新的滑动窗口的最大值
                max = nums[i]; // 初始化最大值
                // 循环找最大值
                for (int j = i + 1; j < (i + k); j++) {
                    max = Math.max(max,nums[j]);
                }
            } else {
                // 3.只需要用滑动窗口的最大值和新增值比较即可
                max = Math.max(max,nums[i + k - 1]);
            }
            // 最终的返回数组记录
            res[i] = max;
            // 记录下轮要移除的元素
            r = nums[i];
        }
        return res;
    }
}

Submit the above code to leetcode, and the execution results are as follows:

In fact, we can use "queue" to realize this problem. Its implementation idea is also very simple, even more convenient than violent solution. Let's continue to look at it next.

Implementation method 3: priority queue

Another classic solution to this problem is to use the maximum heap. The structure of the maximum heap is as follows:

We can put the value of the sliding window into the maximum heap, so we can directly obtain the maximum value of the sliding window by using the characteristics of this data structure (it will put the maximum value on the top of the heap). The implementation code is as follows:

class Solution {
    public int[] maxSlidingWindow(int[] nums,int k) {
        // 非空判断
        if (nums == null || k <= 0) return new int[]{};
        // 最终结果数组
        int[] res = new int[nums.length - k + 1];
        // 优先队列
        PriorityQueue<Integer> queue = new PriorityQueue(res.length,new Comparator<Integer>() {
            @Override
            public int compare(Integer i1,Integer i2) {
                // 倒序排列（从大到小，默认是从小到大）
                return i2 - i1;
            }
        });
        // 第一轮元素添加
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }
        res[0] = queue.peek();
        int last = nums[0]; // 每轮要移除的元素
        for (int i = k; i < nums.length; i++) {
            // 移除滑动窗口之外的元素
            queue.remove(last);
            // 添加新元素
            queue.offer(nums[i]);
            // 存入最大值
            res[i - k + 1] = queue.peek();
            // 记录每轮要移除的元素（滑动窗口最左边的元素）
            last = nums[i - k + 1];
        }
        return res;
    }
}

Code interpretation

As can be seen from the above code, the corresponding data structure of the largest heap in Java is the priority queue, but the default sorting rule of the priority queue is from small to large, Therefore, we need to create a comparator to change the sorting rules (from large to small), and then put all elements of the sliding window into the priority queue, so that we can directly use queue. Peek() to get the maximum value of the sliding window, and then recycle to remove the edge value of the sliding window, so as to solve this problem.

Submit the above code to leetcode, and the execution results are as follows:

Implementation method 4: double ended queue

In addition to 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 it does not need to maintain the element position every time when adding and deleting, so its execution efficiency will be very high.

The core of the dual end queue implementation idea is to always place the maximum value of the sliding window at the head of the queue (that is, the leftmost part of the queue), which will be less than the maximum value and to the left of the maximum value Delete all elements (in the direction of the team leader). This is also well understood because these relatively small values are not as large as the maximum value, but also ahead of the maximum value, that is, their life cycle is shorter than the maximum value. Therefore, we can delete these relatively small elements directly, as shown in the figure below:

The process of realizing the maximum value of sliding window by double ended queue is divided into the following four steps:

The implementation code is as follows:

class Solution {
    public int[] maxSlidingWindow(int[] nums,int k) {
        // 非空判断
        if (nums == null || k <= 0) return new int[0];
        // 最终结果数组
        int[] res = new int[nums.length - k + 1];
        // 存储的数据为元素的下标
        ArrayDeque<Integer> deque = new ArrayDeque();
        for (int i = 0; i < nums.length; i++) {
            // 1.移除左边超过滑动窗口的下标
            if (i >= k && (i - k) >= deque.peek()) deque.removeFirst();

            // 2.从最后面开始移除小于 nums[i] 的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
                deque.removeLast();

            // 3.下标加入队列
            deque.offer(i);

            // 4.将最大值加入数组
            int rindex = i - k + 1;
            if (rindex >= 0) {
                res[rindex] = nums[deque.peek()];
            }
        }
        return res;
    }
}

Submit the above code to leetcode, and the execution results are as follows: