2025/10/16
思路:一开始先找出最大值的位置,用指针指出来。每次滑动,先看最大值位置是不是在窗口最左边,如果是,则直接求一遍新窗口的最大值;如果不是,让新来的和上一个窗口最大值比较,看看是否要更新指针和最大值。
评价:这比暴力遍历好一点,但最坏情况还是 \(O(n*k)\)
推荐思路:双端单调队列,队头元素如果滑出窗口 → 弹出队头 2. 新元素加入时 → 弹出所有比它小的队尾元素 3. 队头即为当前窗口最大值
Sliding Window Maximum
思路:一开始先找出最大值的位置,用指针指出来。每次滑动,先看最大值位置是不是在窗口最左边,如果是,则直接求一遍新窗口的最大值;如果不是,让新来的和上一个窗口最大值比较,看看是否要更新指针和最大值。
评价:这比暴力遍历好一点,但最坏情况还是 \(O(n*k)\)
推荐思路:双端单调队列,队头元素如果滑出窗口 → 弹出队头 2. 新元素加入时 → 弹出所有比它小的队尾元素 3. 队头即为当前窗口最大值