leetcode-239-Sliding-Window-Maximun

发表于 | 更新于: | 分类于 |

1. 题目

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

返回滑动窗口最大值。

示例:

输入: 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
注意：

你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。

进阶：

你能在线性时间复杂度内解决此题吗？

2. 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        # 滑窗使用双端队列(deque)数据结构，且只存下标
        # 这个队列中，队首为最大元素的下标，之后的元素都比队首小
        window = []
        
        # 存每一个滑窗中的最大值，最后返回
        res = []
        
        # 检验参数是否有非法情况
        if k > len(nums) or len(nums) == 0 or k == 0:
            return res
        
        for i in range(len(nums)):
            
            # step1：滑窗移动
            
            # 使用下标控制滑窗范围
            # 滑窗移动一格，导致队首元素从滑窗离开，则从deque的头部出队
            # 注意: 1 window存的是下标；
            #       2 i为待进队的元素下标；
            #       3 待进队元素，在满足所有逻辑判断条件之后，才进队
            # i-k是window左界：0 window[1 2 3] 4,此时i=4,k=3
            # window移动一格后为 0 1 window[2 3 4]，即window[0]出队，腾出空间给4进队
            
            if len(window) > 0 and window[0] <= i - k:
                window.pop(0)
                
            # step2：维护deque
            
            # 只要deque中有比待入队元素小的值，则从队尾移除
            # 即，deque中，只保存可能是最大值的下标
            
            while len(window) > 0 and nums[i] > nums[window[-1]]:
                window.pop()
                
            # 满足逻辑判断之后，新元素下标入队
            window.append(i)
            
            # 弹出滑窗中最大的元素
            if i >= k - 1:
                res.append(nums[window[0]])
        
        return res
		
		
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []
        if len(nums) == 0 or k == 0 or k > len(nums):
            return res
        for i in range(len(nums)):
            if i+k <= len(nums):
                res.append(max(nums[i:i+k]))
        return res