239. Sliding Window Maximum

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

solution

• 暴力法

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) < k:
            return None
        
        res = []
        for i in range(k, len(nums)+1):
            res.append(max(nums[i-k: i]))
        return res

时间复杂度：O(n × k) 空间复杂度：O()

• 单调队列 Monotonic Queue

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:      
        q = collections.deque()  # 和单调栈一样，队列中保存的是indices
        res = []
        for i, cur in enumerate(nums):
            while q and nums[q[-1]] <= cur:
                q.pop()
            q.append(i)
            # 特别之处在这里: 超过滑动滑口的部分pop出去
            if q[0] == i - k:
                q.popleft()
            # if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
            if i >= k - 1:
                res.append(nums[q[0]])
        return res

class MyQueue(object):
    def __init__(self):
        self.q = collections.deque()
    
    def pop(self, value):
        # 保证队列里是单调的，非空且等于出口时弹出
        # 这里是if 和 q[0]，我自己写的while 和 q[-1], 这里多写大于等于更是问题了
        if self.q and value == self.q[0]:
            self.q.popleft()
        
    def push(self, value):
        # 非空，push的值大于最小值时，一直弹出
        # 该value位置之前比他小的肯定是没用的了, 注意是>。等于的先留着？
        while self.q and value > self.q[-1]:
            self.q.pop()
        self.q.append(value)
    
    @property
    def front(self):  # 当前队列最大值, 第0
        return self.q[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = MyQueue()
        res = []
        for i in range(k):
            q.push(nums[i])
        
        res.append(q.front)
        for i in range(k, len(nums)):
            q.pop(nums[i - k])  # 关键是要想到这里，所以单调队列的pop是带元素的
            q.push(nums[i])
            res.append(q.front)
        return res        

时间复杂度：O(n) 空间复杂度：O()

• 堆

  • 由于该滑动窗口的窗口值是固定的，因此曾想过用堆来做。问题是这个窗口是移动的，而大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。不能用大顶堆

follow up

480. Sliding Window Median