0239. Sliding Window Maximum.md

• 239. Sliding Window Maximum.md
• 难度：Hard
• 相关知识点：Array | Queue | Sliding Window|Heap (Priority Queue) | Monotonic Queue /ˌmɔnə'tɔnik/
• 题目链接：[https://leetcode.com/problems/longest-substring-without-repeating-characters/description/]

You are given an array of integers 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 1:

Input: nums = [1,3,-1,-3,5,3,6,7], 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
Example 2:

Input: nums = [1], k = 1
Output: [1]
 

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

Solution1 : Monotonic Queue

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max_queue = deque()
        ans = []
        for i in range(len(nums)):
            while max_queue and max_queue[0] < i - k + 1: # 超过k需要去掉
                max_queue.popleft()
            
            while max_queue and nums[max_queue[-1]] < nums[i]: 
                max_queue.pop() # 维护 q 的单调性

            max_queue.append(i)
            if i >= k - 1:
                ans.append(nums[max_queue[0]])
        return ans

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque()
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)

        ans = [nums[q[0]]]
        for i in range(k, n):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            while q[0] <= i - k:
                q.popleft()
            ans.append(nums[q[0]])
        
        return ans

Solution2: Heap

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        heap = []
        ans = []
        heap = [(-nums[i], i) for i in range(k)]
        heapq.heapify(heap)
        ans.append(-heap[0][0])
        
        for i in range(k, len(nums)):
            heapq.heappush(heap, (-nums[i], i))
            while heap[0][1] <= i - k:
                heapq.heappop(heap)

            ans.append(-heap[0][0])

        return ans