"239 Sliding Window Maximum Value" on the 16th day of LeetCode brushing

LeetCode239滑动窗口最大值

滑动窗口：The concept should be a sliding window protocol that originated in computing networks,is used to control flow.而在算法题中,The sliding window technique is commonly used in strings and arrays to obtain some extreme values ​​of substrings or subarrays,You can see more vivid topics about sliding windowsleetCode上《和为s的连续正数序列》.

题目描述

定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧.你只可以看到在滑动窗口内的 k 个数字.滑动窗口每次只向右移动一位.

返回滑动窗口中的最大值.

进阶：Can you solve this problem in linear time complexity？

示例

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[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

题目解析

At the beginning, it was said in the title that the maximum value of the sliding window was returned,But the output given in the example is again an array,So what is returned here is actually an array of the maximum values ​​in each sliding window.That is, we need to take out the maximum value in the window element every time the window slides,直到最后一个元素.

解法1：

In fact, it is very easy to solve the problem using a brute force algorithm,The outermost loop is from0遍历到nums.length - k + 1(The right border of the last window just reaches the last element).The inner loop recalculates the maximum value in the sliding window every time,即计算k个元素的最大值.代码如下：

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        if (nums.length * k == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];    //The length of the final returned array can be calculated in advance
        for (int i = 0; i < nums.length - k + 1; i++) {
    
            int max = Integer.MIN_VALUE;
            for (int j = i; j < k + i; j++) {
    
                max = Math.max(max, nums[j]);
            }
            result[i] = max;
        }
        return result;
    }
}

leetCodeThe time limit was exceeded when submitting,Obviously its time complexity is O(len*k);

解法2

Since the title prompts us to use a linear time problem to solve,Then you can only get the answer you want when you can only think of one way to traverse it once.See the big guy talking about a use of double-ended queues（In and out at the beginning and end）的方式来进行求解,大致思路如下：

1、 使用一个队列,Each time the element is enqueued,If the current element enters the queue,is larger than an element in the queue,Then dequeue these smaller elements,Then enqueue the element.In this way, each judgment operation can ensure that the elements in the queue are arranged in descending order.（Note that it is also possible to delete all elements in the queue during this operation）

2、从i = k - 1开始,iThe subscript index of the traversed array,每次取得队头元素（Because the head element is the largest）,Add to the result array to be returned.

下面看一张图（大佬画的,It's so clear,原文链接《滑动窗口最大值》）

 
程序实现代码如下,java语言实现的,It uses its built-in collections framework：

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
		if (nums.length * k == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];
        int cnt = 0;
        List<Integer> deQueue = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
    
           while (deQueue.size() > 0 && nums[i] > deQueue.get(deQueue.size() - 1)) {
    		//Put the teaching value in the appropriate place
               deQueue.remove(deQueue.size() - 1);
           }
           deQueue.add(nums[i]);
           if (i >= k && nums[i - k] == deQueue.get(0)) {
    	//If the current queue element hask个,则将队头元素出队,Because the next window won't contain this element anymore,且 //This is possible because, as mentioned earlier, the elements in the queue are stored in descending order.
               deQueue.remove(0);
           }
           if (i >= k - 1) {
    	//从i = k - 1开始,Add the head of line element to the result
               result[cnt++] = deQueue.get(0);
           }

        }
        return result;
    }
}

程序运行结果：

执行用时：96ms 超过16%的java提交记录

内存消耗：53.7MB,超过6%的java提交记录

 
The result of the above operation is not very ideal,The reason should be that you need to be right when using the queueint和IntegerCarry out packing and sealing operations,In fact, we can completely follow the above ideas,Use an array to simulate the actions of the queue,Just set the head and tail pointers more.代码如下：

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        if (nums.length * k == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];
        int[] deQueue = new int[nums.length + 1];		//Use an array to simulate a deque
        int cnt = 0, front = 0, rear = 0;
        for (int i = 0; i < nums.length; i++) {
    
            while (front != rear && nums[i] > deQueue[rear - 1]) {
    
                rear--;	//队尾元素出队
            }
            deQueue[rear++] = nums[i];
            if (i >= k && nums[i - k] == deQueue[front]) {
    
                front++;	//队头元素出队
            }
            if (i >= k - 1) {
    	//取得队头元素
                result[cnt++] = deQueue[front];
            }
        }
        return result;
    }
}

You can see that the overall framework of the program is almost exactly the same,But much faster：

执行用时：10ms 打败88%的java提交记录

内存消耗：59.9MB