[LeetCode] 239. Sliding Window Maximum

本文主要是介绍[LeetCode] 239. Sliding Window Maximum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/sliding-window-maximum/description/

题目

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.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position Max
————— —–
[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

Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

思路

思路1

nums中用k个窗口扫描过，每个窗口进行排序，获取最大值，时间复杂度可以达到 nlogk。

思路2

使用排序算法是为了产生一个实时变化、k个元素的优先队列。
为了实现 n的时间复杂度，元素的扫描次数应该固定的。
这里的技巧在于这个优先队列的设计。
该优先队列的特征：
1. 优先队列降序。
算法过程：
1. 队首元素的下标超过窗口的最左边就踢出。
2. 除去队列中比当前元素小于等于的元素。由于是优先队列，可以从队尾开始比较。
3. 将当前元素加入队尾。
4. 队首就是所求的最大值。

为了便于计算队列中存储的是元素在nums中的下标。

code

方法二

Your runtime beats 55.38 % of python3 submissions.

class Solution:def maxSlidingWindow(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""priorityQueue = []res = []for i in range(len(nums)):while len(priorityQueue)!=0 and priorityQueue[0] <= i-k:del priorityQueue[0]while len(priorityQueue)!=0 and nums[priorityQueue[-1]]<=nums[i]:del priorityQueue[-1]priorityQueue.append(i)if i+1-k>=0:res.append(nums[priorityQueue[0]])return res