题目

给定一个数组 nums ，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

  1. 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
  2. 输出: [3,3,5,5,6,7] 
  3. 解释: 
  4.   滑动窗口的位置                最大值
  5. ---------------               -----
  6. [1  3  -1] -3  5  3  6  7       3
  7.  1 [3  -1  -3] 5  3  6  7       3
  8.  1  3 [-1  -3  5] 3  6  7       5
  9.  1  3  -1 [-3  5  3] 6  7       5
  10.  1  3  -1  -3 [5  3  6] 7       6
  11.  1  3  -1  -3  5 [3  6  7]      7

代码实现

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # nums = [1, 3, -1, -3, 5, 3, 6, 7]
        # how to get max value among the window
        # use maximum heap (-value, index) 

        # Time complexity : O(NlogN)
        # Space complexity: O(N)

        res, heap = [], []
        for i in range(len(nums)):
            heapq.heappush(heap, ( -nums[i], i))
            if i + 1 >= k:
                while heap and heap[0][1] <  i + 1 - k:
                    heapq.heappop(heap)
                res.append(-heap[0][0])
        return res

作者：frankchen250

链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/python-heap-by-frankchen250/