题目

给出一个可能包含重复的整数数组，和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。

样例

给出数组 [1,2,7,7,8], 滑动窗口大小为 k = 3. 返回 [7,7,8].

解释：

最开始，窗口的状态如下：

[|1, 2 ,7| ,7 , 8], 最大值为 7;

然后窗口向右移动一位：

[1, |2, 7, 7|, 8], 最大值为 7;

最后窗口再向右移动一位：

[1, 2, |7, 7, 8|], 最大值为 8.

Challenge:

O(n)时间,O(k)的额外空间

思路

牛客网的算法视频有讲解此类型题；

方法一：每次对每个窗口遍历其中的k个数，选出最大值；
方法二：使用双端队列，实现最大值的更新

双端队列

定义双端队列（deque，全名double-endedqueue）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

操作：从右边加入，从左边弹出的操作

python中双端队列的操作函数；

先调用模块

from collections import deque #首先从collections 模块中导入deque类

定义一个双端队列和操作

A=deque([]) #创建一个空的双队列
A.append(n) #从右边像队列中增加元素 ，n表示增加的元素
A.appendleft(n) #从左边像队列中增加元素，n表示增加的元素
A.clear() #清空队列
A.count(n) #在队列中统计元素的个数，n表示统计的元素
A.extend(n) #从右边扩展队列，n表示扩展的队列
A.extendleft(n) #从左边扩展队列，n表示扩展的队列
A.pop() #从队列的右边删除元素，并且返回删除值
A.popleft() #从队列的左边删除元素，并且返回删除值

方法二思路

定义一个双端队列qmax，存放数组中nums中的下标，初始qmax.append(0);定义一个存放每次窗口最大值res
取当前nums[1:]的的下标和nums值，为x,y，初始为1,nums[1]
判断qmax队尾存储的下标j,如果nums[j] > y,直接把下标x放进qmax队尾中;如果nums[j] <=y ,则一直从qmax的队尾弹出直到某个下标在qmax中对应的值大于y，此时把x放在qmax的队尾中.
执行一次步骤3，判断是否有过期的数(不属于当前k范围内的数)在qmax的队头中，有则popleft()删除该队头；然后存储当前窗口的最大值，即qmax的队头在res中。
使x = x+1 ;nums[y+1]，执行步骤3和4直到达到nums的最后一个下标和值。

Python实现

Python

from collections import deque
class Solution:
    """
    @param: nums: A list of integers
    @param: k: An integer
    @return: The maximum number inside the window at each moving
    """
    def maxSlidingWindow(self, nums, k):
        # write your code here
        #特殊情况，k=1，则每个都最大
        if k == 1:
            return nums
        #新建一个双端队列qmax，初始值为0
        #res存放每次移动的最大结果
        qmax = deque([])
        qmax.append(0)
        res = []

        for x,y in enumerate(nums[1:],1):
            """
            x,y表示当前的下标和nums值；
            判断qmax队尾存储的下标j,
            如果nums[j] > y,直接把下标x放进qmax队尾中;
            如果nums[j] <=y ,则一直从qmax的队尾弹出直到某个下标在qmax中对应的值大于y，
            此时把x放在qmax的队尾中.
            """
            if nums[qmax[-1]] <=y:
                for i in range(len(qmax)-1,-1,-1):
                    if nums[qmax[i]] > y:
                        break
                    else:
                        qmax.pop()         
            qmax.append(x) 
            #当qmax存在过期数据，即不在移动k范围内的，将其移除出双端队列
            if qmax[0] <= x-k:
                qmax.popleft()
            #将每次移动窗口的最大值存储到res中
            if x >=k-1:
                res.append(nums[qmax[0]])
        return res

Java实现

一开始考虑使用栈来实现,每次推入新值,从stack的peek开始推出比当前值小的数,但是发现【5,8,6,7 ,4,3】,k = 3时,推入4,8被推出,但是6,7都比4大没被推出,但是6<7应该被推出,所以需要遍历一遍缓存的数,保证peek是当前最大值,这样时间复杂度O(nklogk),不符合要求了。

然后使用双端队列,每次推入新值时,保证deque内长度小于等于k,在peekLast推出比当前小的值,以此保证peekFirst一直是最大值。

双端队列的文档
我觉得难点应该就是双端队列的使用吧,时间复杂度可能写的不对-_-||

Java

public class Solution {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && i - deque.peekFirst() >= k) {
                // 如果队列头部的元素已经超出滑动窗口的范围，就将头部元素退出
                deque.pollFirst();
            }
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                // 如果新来的元素比队列最后一个元素大，则将最后一个元素退出
                deque.pollLast();
            }
            deque.offerLast(i);
            if (i >= k - 1) {
                // 如果遍历的元素已经达到一个滑动窗口的大小，就开始提取窗口的最大值了
                result.add(nums[deque.peekFirst()]);
            }
        }
        return result;
    }
}

题目链接

本文由 Time 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 31, 2018 at 12:27 am

滑动窗口的最大值

题目

样例

思路