Leetcode 239. Sliding Window Maximum(python)

题目

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]

Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.
Follow up:
Could you solve it in linear time?

解法1：brutal force

class Solution(object):def maxSlidingWindow(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""if not nums:return []n = len(nums)ans = []for i in range(n-k+1):curr_max = max(nums[i:i+k])ans.append(curr_max)return ans

时间复杂度：O(N*K)
空间复杂度：O(1)
提交结果超过了%14的用户

解法2：利用单调递减双向队列

算法流程：

• 构建一个双向队列，使之以递减的方式排列，最大的元素为q[0]，最小的元素为q[-1]
• 具体的方法为，当碰到一个新元素的时候，如果现在q中的元素已经达到k，那么应该把q[0]弹出，因为现在的window已经不能包括q[0]了
• 从队列末尾开始遍历，pop出所有比当前元素小的成员，然后append现在这个元素，这样可以保证append新元素之后队列依旧是单调递减
• 当前window中的最大值为当前队列中的第一个元素

class Solution(object):def maxSlidingWindow(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""if not nums:return []n = len(nums)q = collections.deque()q.append(0)for i in range(1,k-1):while q and nums[q[-1]]<=nums[i]:q.pop()q.append(i)ans = []for i in range(k-1,n):if q[0] == i-k:q.popleft()while q and nums[q[-1]]<=nums[i]:q.pop()q.append(i)ans.append(nums[q[0]])return ans

时间复杂度：O(N)，乍一看这也应该是个O(N*K)的复杂度，因为每一个位置在最差的情况下可能会循环K次，但其实这种想法是不成立的。换个角度来想，这种方法，每种元素都会最多被访问两次，所以复杂度是O(2N)=O(N)
空间复杂度：O(K)
提交结果超过了%76的用户

解法3：动态规划，构建左右最大数组

这种解法有点类似leetcode238的思想，时间复杂度也是linear的，但是这种方法的提交结果比方法2更快，但是实际上这种方法应该便利了3次整个数组的，就有点奇怪。有兴趣的话可以参考leetcode的官方solution

class Solution(object):def maxSlidingWindow(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""n = len(nums)if not nums:return []if k==1:return numsleft = [0]*nleft[0] = nums[0]right = [0]*nright[0] = nums[-1]for i in range(1,n):if i%k == 0:left[i] = nums[i]else:left[i] = max(left[i-1],nums[i])j = n-i-1if (j+1)%k == 0:right[j] = nums[j]else:right[j] = max(right[j+1],nums[j])ans = []for i in range(n-k+1):ans.append(max(left[i+k-1],right[i]))return ans

时间复杂度：O(N)
空间复杂度：O(N)
提交结果超过了%92的用户