Day19 - 239. 滑动窗口最大值

题目链接：https://leetcode.cn/problems/sliding-window-maximum/description/

1.问题理解

• 场景有一个数组 nums 和一个窗口大小 k，窗口从数组左边滑到右边，每次滑动一格。你需要记录每次窗口停下时，窗口内的最大值。

  • 示例：nums = [1,3,-1,-3,5,3,6,7], k=3
    第一个窗口 [1,3,-1] 的最大值是 3，第二个窗口 [3,-1,-3] 的最大值还是 3……最后结果是 [3,3,5,5,6,7]

2.核心算法：单调队列

• 为什么用单调队列？

暴力解法重复计算了窗口中的值，而单调队列通过维护一个递减的队列，保证队头永远是当前窗口的最大值，避免重复比较

• 算法步骤：

• 1.初始化：一个双端队列kept_nums，结果立碑max_list

• 2.遍历数组：

  • 新元素nums[i]入队时，从队尾弹出所有比它小的数（之前的数），而之前加入进来又比它小的数不可能是后续窗口的最大值

  • 将nums[i]加入队尾（从队尾加入（右->左））

  • 如果队头元素是原窗口左侧刚滑过去的元素，则弹出队头(比如原窗口从 [5,3,1] 右移到 [3,1,4] 时，原左侧的 5 需要被移除。)

  • 当窗口完全形成（假如k=3），队头就是当前窗口最大值(比如原窗口[5,3,1] 完全形成后，队头就是 5,5 就是最大值)

3.关键点和边界条件

• 关键点：

  • 单调性：队列必须严格单调递减，队头必须是最大值

  • 过期处理：队头元素可能因原窗口滑动失效，需要及时移除

• 边界条件：

  • 空数组或者k=1（每个窗口只有 1 个数），直接返回原数组

  • k > len(nums)：返回该窗口的最大值

  • 队列清理顺序：先清理队尾，再处理过期队头，最后记录结果

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max_list = [] #结果集
        kept_nums = deque() #单调队列

        for i in range(len(nums)):
            update_kept_nums(kept_nums,nums[i]) #nums新加入的元素

            if i >=k and nums[i-k] == kept_nums[0]: #左侧旧元素如果等于单调队列头元素，需要移除头元素
                kept_nums.popleft()
            if i >= k - 1: #因为 nums 索引是从 0 开始，这里要-1
                max_list.append(kept_nums[0])
        return max_list


    
    
    
def update_kept_nums(kept_nums,num):
    #如果队列里面不为空 并且 新加入的元素大于之前的元素
    while kept_nums and num > kept_nums[-1]:
        kept_nums.pop()

    kept_nums.append(num)