239.md

239 Sliding Window Maximum

Description

link

---

Solution 1 : HEAP

counter是用来判断是否应当去除当前元素，比起直接remove，这种操作只需要使用1的复杂度来实现，只是需要牺牲一点空间复杂度，这种方式在很多题目当中都出现过，需要留心

---

Code 1

Complexity T : O(nlog(n)) M : O(k~n)

class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        cnt, heap, res = collections.Counter(), [], []
        
        for i, num in enumerate(nums):
            heapq.heappush(heap, -num)
            cnt[num] += 1
            while not cnt[-heap[0]]:
                heapq.heappop(heap)
            if i >= k - 1:
                res.append(-heap[0])
                cnt[nums[i - k + 1]] -= 1
        return res

---

Solution 2 : deque

通过保持deque当中的元素有效且递减（存储的为index，方便slide时直接删掉），来获得答案，index和num互换的机制经常用在求固定空间的特定数字上，需要注意

---

Code 2

Complexity T : O(n) M : O(k)

class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        d = collections.deque()
        out = []
        for i, n in enumerate(nums):
            while d and nums[d[-1]] < n:
                d.pop()
            d += i,
            if d[0] == i - k:
                d.popleft()
            if i >= k - 1:
                out += nums[d[0]],
        return out