Leetcode 239. Sliding Window Maximum

Seawolf

1. Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
   
2. 
   
3. Follow up:
   
4. Could you solve it in linear time?
   
5. 
   
6. Example:
   
7. 
   
8. Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
   
9. Output: [3,3,5,5,6,7]
   
10. Explanation:
    
11. 
    
12. Window position                Max
    
13. ---------------               -----
    
14. [1  3  -1] -3  5  3  6  7       3
    
15. 1 [3  -1  -3] 5  3  6  7       3
    
16. 1  3 [-1  -3  5] 3  6  7       5
    
17. 1  3  -1 [-3  5  3] 6  7       5
    
18. 1  3  -1  -3 [5  3  6] 7       6
    
19. 1  3  -1  -3  5 [3  6  7]      7
    
20. 
    
21. 
    
22. Constraints:
    
23. 
    
24. 1 <= nums.length <= 10^5
    
25. -10^4 <= nums[i] <= 10^4
    
26. 1 <= k <= nums.length

复制代码

1. 给定一个数组 nums，有一个大小为k;的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
   
2. 
   
3. 返回滑动窗口中的最大值。
   
4. 
   
5. 
   
6. 进阶：
   
7. 
   
8. 你能在线性时间复杂度内解决此题吗？
   
9. 
   
10. 
    
11. 示例:
    
12. 
    
13. 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
    
14. 输出: [3,3,5,5,6,7]
    
15. 解释:
    
16. 
    
17.   滑动窗口的位置                最大值
    
18. ---------------               -----
    
19. [1  3  -1] -3  5  3  6  7       3
    
20. 1 [3  -1  -3] 5  3  6  7       3
    
21. 1  3 [-1  -3  5] 3  6  7       5
    
22. 1  3  -1 [-3  5  3] 6  7       5
    
23. 1  3  -1  -3 [5  3  6] 7       6
    
24. 1  3  -1  -3  5 [3  6  7]      7
    
25. 
    
26. 提示：
    
27. 
    
28. 1 <= nums.length <= 10^5
    
29. -10^4<= nums[i]<= 10^4
    
30. 1 <= k<= nums.length

复制代码

1. from collections import deque
   
2. class Solution:
   
3.     def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
   
4.         queue = deque()
   
5.         res = []
   
6.         if len(nums) == 0:
   
7.             return res
   
8.         for i in range(k - 1):
   
9.             self.indeque(queue, nums[i])
   
10.         for i in range(k - 1, len(nums)):
    
11.             self.indeque(queue, nums[i])
    
12.             res.append(queue[0])
    
13.             self.outdeque(queue, nums[i - k + 1])
    
14.         return res
    
15.    
    
16.     def indeque(self, queue: List[int], num: int) -> None:
    
17.         while len(queue) != 0 and queue[-1] < num:
    
18.             queue.pop()
    
19.         queue.append(num)
    
20.    
    
21.     def outdeque(self, queue: List[int], num: int) -> None:
    
22.         if queue[0] == num:
    
23.             queue.popleft()

复制代码