動機

從sliding window到寫merge interval的變化版

Problem

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 = 3Output: [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 = 1Output: [1]

Example 3:

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

Example 4:

Input: nums = [9,11], k = 2Output: [11]

Example 5:

Input: nums = [4,-2], k = 2Output: [4]

 

Constraints:

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

Sol1: heapq

除了heapq去排序，還要一個hash去紀錄出現次數，以免heapq的最大值其實已經不再windows中了

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        maxQ = []
        cnt = {}
        ret = []
        for i in range(k):
            heappush(maxQ, -nums[i])
            if nums[i] not in cnt:
                cnt[nums[i]] = 1
            else:
                cnt[nums[i]] += 1
        
        i = k
        while maxQ and i <= len(nums):
            ret.append(-maxQ[0])
            cnt[nums[i-k]] -= 1
            while maxQ and cnt[-maxQ[0]] == 0:
                heappop(maxQ)
            if i < len(nums):
                heappush(maxQ, -nums[i])
                if nums[i] not in cnt:
                    cnt[nums[i]] = 1
                else:
                    cnt[nums[i]] += 1
            i += 1
        return ret

Sol2: deque

與寫merge interval很像，但是多一個條件，第一個值必須是在range中

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        ret = []
        for i in range(len(nums)):
            if q and q[0] == i-k: # promise1: q[0] is max & in [i-k+1:i+1]
                q.popleft()
            while q and nums[q[-1]] <= nums[i]: # promise2: q[0] > q[1] > ....
                q.pop()
            q.append(i)
            if i >= k-1:
                ret.append(nums[q[0]])
        return ret