129. 滑动窗口最大值

题目

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

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

题解

核心思路：单调队列

如果我们使用暴力法，每次遍历窗口内的 \(k\) 个元素找最大值，时间复杂度是 \(O(N \cdot k)\)。为了优化到 \(O(N)\)，我们需要一个能够在 \(O(1)\) 时间内获取当前窗口最大值，并能随着窗口移动高效更新的数据结构。

单调队列（双端队列 Deque）非常适合解决这个问题。我们维护一个队列，队列中存储的是数组的下标（注意是下标，不是数值，为了判断是否滑出窗口），并且保证队列内的数值是**单调递减**的。

为什么保持单调递减？

假设窗口内有两个元素 \(nums[i]\) 和 \(nums[j]\)，其中 \(i < j\)（\(i\) 在 \(j\) 左边，即 \(i\) 更早进入窗口）。

如果 \(nums[i] \le nums[j]\)，那么只要 \(nums[j]\)在窗口内，\(nums[i]\) 就永远不可能成为最大值了（因为 \(nums[j]\) 比它大，而且比它存活得更久）。

所以，当遇到一个更大的新元素时，前面比它小的元素都可以被“淘汰”掉。

算法流程

我们要遍历数组 \(nums\)，对于每一个索引 \(i\)：

入队前清理（保持单调性）：

如果队列不为空，且当前元素 \(nums[i]\)大于等于队尾下标对应的元素 \(nums[deque.back()]\)，则将队尾元素弹出。重复此过程，直到队列为空或队尾元素大于当前元素。

目的：保证队列头部始终是当前窗口的最大值。

入队：

将当前索引 \(i\) 加入队尾。

检查窗口边界（移除过期元素）：

检查队头下标 \(deque.front()\) 是否已经滑出了窗口（即 \(deque.front() \le i - k\)）。如果是，将队头弹出。

记录结果：

当 \(i \ge k - 1\)时（即窗口已经形成），将队头下标对应的元素 \(nums[deque.front()]\) 加入结果数组。

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        # 双端队列，用于存储下标
        q = deque()
        result = []
        
        for i in range(len(nums)):
            # 1. 入队前清理：保持队列单调递减
            # 如果当前元素比队尾元素大，那么队尾元素在当前及以后的窗口中都不可能是最大值了
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            
            # 2. 入队：存入当前下标
            q.append(i)
            
            # 3. 检查窗口边界：如果队首下标已经出了窗口左边界，则移除
            # 当前窗口范围是 [i-k+1, i]，如果 q[0] < i-k+1 (即 q[0] <= i-k)，说明过期
            if q[0] == i - k:
                q.popleft()
            
            # 4. 记录结果：当窗口完全形成后（i >= k-1），队首就是当前窗口最大值
            if i >= k - 1:
                result.append(nums[q[0]])
                
        return result

时间复杂度：\(O(N)\)虽然代码里有 while循环，但每个元素最多被加入队列一次（append），也最多被弹出队列一次（pop）。因此总的操作次数与数组长度成正比。
空间复杂度：\(O(k)\) 双端队列中最多存储 \(k\) 个元素的下标（在最坏情况下，即数组是严格单调递减时）。

示例推导

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3

i	当前元素	队列操作 (存下标)	队列状态 (对应值)	结果 (队头值)	说明
0	1	1入队	`[1]`	-	窗口未满
1	3	3 > 1, 弹1; 3入队	`[3]`	-	3把1淘汰了
2	-1	-1 < 3, -1入队	`[3, -1]`	3	窗口 `[1,3,-1]`, max=3
3	-3	-3 < -1, -3入队	`[3, -1, -3]`	3	窗口 `[3,-1,-3]`, max=3
4	5	5 > -3, 弹; 5 > -1, 弹; 5 > 3, 弹; 5入队	`[5]`	5	3过期(下标0)其实早该移出，但这里5把前面的全淘汰了
5	3	3 < 5, 3入队	`[5, 3]`	5	窗口 `[-3,5,3]`, max=5
6	6	6 > 3, 弹; 6 > 5, 弹; 6入队	`[6]`	6	窗口 `[5,3,6]`, max=6
7	7	7 > 6, 弹; 7入队	`[7]`	7	窗口 `[3,6,7]`, max=7

输出: [3, 3, 5, 5, 6, 7]

附近最大值

题目

题目描述

给定一个可能含有重复值的数组 \(arr\)，找到每一个\( i \)位置左边和右边离 \(i \)位置最近且值比 \(arr[i] \)小的位置。返回所有位置相应的信息。

输入描述:
    第一行输入一个数字 \(n\)，表示数组 \(arr\) 的长度。
    以下一行输入 \(n \)个数字，表示数组的值
输出描述:
    输出n行，每行两个数字 \(L\) 和 \(R\)，如果不存在，则值为 -1，下标从 0 开始。
示例1
    输入
    7
    3 4 1 5 6 2 7
    输出
    -1 2
    0 2
    -1 -1
    2 5
    3 5
    2 -1
    5 -1

题解

题目要求找 “左边和右边离\( i \)最近且值比 \(arr[i] \)小的位置”。

这正是单调栈最擅长的领域：Next Less Element (NLE) / Previous Less Element (PLE) 问题。

我们需要维护一个单调递增栈（栈底小，栈顶大）。

逻辑如下：

当我们要把一个元素 \(arr[i]\) 放入栈时：

1. 如果 \(arr[i]\) 比栈顶元素 \(top\) 大：直接入栈。因为 \(arr[i]\) 可能是 \(top\)右边第一个比它大的，但题目找小的，所以暂时没触发结算。

2. 如果 \(arr[i]\) 比栈顶元素 \(top\) 小：

* 这就意味着 \(arr[i]\) 是 \(top\) 右边第一个比它小的数（Right Less Element）。

* 同时，由于栈是单调递增的，\(top\) 下面的那个元素（设为 \(stack[-2]\)）就是 \(top\) 左边第一个比它小的数（Left Less Element）。

* 此时，\(top\) 这个位置的左右答案都找到了，可以弹出 \(top\) 并记录答案。

处理重复值（难点）

题目明确说“可能含有重复值”。这是这道题唯一的坑点。

例如 [3, 4, 4, 5]，当处理第二个 4时，栈里已经有 4 了。

策略：如果 arr[i] == arr[stack.top()]，我们可以把下标压入同一个栈位置（即栈里存的是下标列表 List[int]），或者更通用的做法是：遇到相等的也弹出，但在最后结算时修正，或者使用链表法（栈中存链表）。

最简单的重复值处理策略（修正法）：

1. 遇到 arr[i] < arr[top]时弹出 top。此时 i是 top的右边最近小于值。

2. 遇到 arr[i] == arr[top]时，通常有两种做法：

做法 A（推荐）：把下标连在一起。栈中元素不再是 int，而是 List[int]。比如栈里是 [[0], [1, 2]]表示值 arr[0]最小，arr[1]和 arr[2]相等且比 arr[0]大。当弹出一组下标时，它们的右边最近小于都是当前 i，左边最近小于都是栈中下面那组的最后一个下标。
做法 B：不处理，照样压栈。但在计算“左边最近”时，如果发现左边那个值和自己相等，就继续往左找。这种最坏复杂度会退化到 \(O(N^2)\)，不推荐。

import sys

def getNearLess(arr):
    n = len(arr)
    # 结果数组，初始化为 -1
    # res[i][0] 是左边最近小于，res[i][1] 是右边最近小于
    res = [[-1, -1] for _ in range(n)]
    
    # 单调递增栈，存的是下标的列表 [index1, index2...]
    # 这些下标对应的值是相等的
    stack = []
    
    for i in range(n):
        # 当当前值 < 栈顶代表的值时，触发弹出结算
        while stack and arr[stack[-1][0]] > arr[i]:
            pop_idxs = stack.pop()
            # 栈顶这批下标的右边最近小于就是当前 i
            # 左边最近小于就是新栈顶列表的最后一个下标（如果栈不空）
            left_less_index = stack[-1][-1] if stack else -1
            for idx in pop_idxs:
                res[idx][0] = left_less_index
                res[idx][1] = i
        
        # 如果当前值 == 栈顶值，合并进去
        if stack and arr[stack[-1][0]] == arr[i]:
            stack[-1].append(i)
        else:
            # 否则新建一个列表压入
            stack.append([i])
            
    # 遍历结束后，栈里可能还有元素
    # 这些元素的右边没有比它小的了（否则早被弹出了），所以右边保持 -1
    while stack:
        pop_idxs = stack.pop()
        left_less_index = stack[-1][-1] if stack else -1
        for idx in pop_idxs:
            res[idx][0] = left_less_index
            res[idx][1] = -1
            
    return res

# 处理输入输出
if __name__ == "__main__":
    # 读取所有输入
    input_data = sys.stdin.read().split()
    if not input_data:
        exit()
        
    n = int(input_data[0])
    arr = [int(x) for x in input_data[1:]]
    
    result = getNearLess(arr)
    
    for l, r in result:
        print(f"{l} {r}")

示例推导 (带重复值)

假设输入：3 4 4 2

下标：0 1 2 3

i=0, val=3: 栈 [[0]]
i=1, val=4: 4 > 3, 入栈。栈 [[0], [1]]
i=2, val=4: 4 == 4, 合并。栈 [[0], [1, 2]]
i=3, val=2: 2 < 4, 触发弹出 [1, 2]。

- 对于下标 1 和 2：
  - 右边最近小于：当前 i=3(值2)。
  - 左边最近小于：栈顶剩下 [[0]]，取最后一个下标 0。
- 结果更新：res[1]=[0, 3], res[2]=[0, 3]
- 栈现在是 [[0]]。
- 2 < 3, 触发弹出 [0]。
- 对于下标 0：
  - 右边最近小于：当前 i=3 (值2)。
  - 左边最近小于：栈空了，-1。
- 结果更新：res[0]=[-1, 3]
- 栈空了，2 入栈。栈 [[3]]。

结束：弹出 [3]。

- 右边 -1，左边 -1。
- 结果更新：res[3]=[-1, -1]

复杂度分析

时间复杂度: \(O(N)\)。每个元素最多进栈一次，出栈一次。
空间复杂度: \(O(N)\)。栈和结果数组的空间。

#

!

129. 滑动窗口最大值

题目

题解

算法流程

示例推导

附近最大值

题目

题解

示例推导 (带重复值)