# 滑动窗口的最大值

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-29%2022%3A32%3A39\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E5%9B%B0%E9%9A%BE\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#困难) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E5%A0%86/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#堆优先队列) [![](https://img.shields.io/static/v1?label=\&message=%E5%8D%95%E8%B0%83%E6%A0%88/%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#单调栈单调队列)

> [滑动窗口的最大值\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788)

**问题简述**

```
给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
窗口大于数组长度或窗口长度为 0 的时候，返回空。
```

**思路1：优先队列**

* 使用优先队列(堆)维护窗口内的最大值;
* 细节:
  * 堆除了要保存值还要保存索引, 用于判断当前的最大值是否还在窗口内;
  * Python 中的默认实现为最小堆, 需要转成最大堆(取相反数);

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:
    def maxInWindows(self , arr: List[int], size: int) -> List[int]:

        if size <= 0 or size > len(arr): return []
        
        import heapq

        # 初始化大顶堆
        h = []
        for i in range(size):
            heapq.heappush(h, (-arr[i], i))  # 默认小顶堆，取相反数使变成大顶堆
        
        ret = [-h[0][0]]
        for i in range(size, len(arr)):
            while h and h[0][1] <= i - size:  # 保证堆顶元素在窗口内
                heapq.heappop(h)
            heapq.heappush(h, (-arr[i], i))
            ret.append(-h[0][0])

        return ret
```

</details>

**思路2：单调队列**

* 使用一个严格单调队列 `q` 保存窗口内值的索引（保存索引，相当于保存了两个信息）；
* 这样每次将队首元素加入结果集即可；当队首元素不在窗口中时，出队；

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:
    def maxInWindows(self , arr: List[int], size: int) -> List[int]:
        # 窗口大于数组长度时
        if size > len(arr): return []
        
        from collections import deque
        
        # 初始化单调队列，严格单调
        q = deque()
        for i in range(size):
            # 当入队元素大于队尾时，队尾出队
            while q and arr[q[-1]] <= arr[i]:  # 这里用 <= 是避免相等时判断
                q.pop()
            q.append(i)  # 队列中保存 索引 而不是值，这样相当于保存了两个信息

        ret = [arr[q[0]]]  # 初始化结果序列
        for i in range(size, len(arr)):
            # 如果队首不在窗口内，则弹出（保存索引的好处）
            if q[0] == i - size:
                q.popleft()
            # 保持单调队列
            while q and arr[q[-1]] <= arr[i]:
                q.pop()
            q.append(i)
            ret.append(arr[q[0]])
        
        return ret
```

</details>