算法的学习笔记—滑动窗口的最大值(牛客JZ59)

在这里插入图片描述

😀前言
滑动窗口问题是常见的算法题型，主要考察如何在限定窗口内找到特定值，比如最大值、最小值等。在这篇文章中，我们将深入分析“滑动窗口的最大值”问题的求解方法，并提供一种实现思路，以帮助大家更好地理解该问题。

🏠个人主页：尘觉主页

文章目录

🥰滑动窗口的最大值
- 题目链接
- 😀问题描述
- ❤️‍🔥解题思路
- - 1. 使用大顶堆求解
  - 2. 时间复杂度分析
- 💝代码实现
- - 代码解释
  - 代码优化建议
- 😄总结

🥰滑动窗口的最大值

题目链接

牛客网

😀问题描述

给定一个整数数组 num 和一个整数 size 代表滑动窗口的大小，需要找到每次窗口滑动时的最大值，最后将所有窗口的最大值组合成一个数组返回。例如，对于数组 {2, 3, 4, 2, 6, 2, 5, 1} 和窗口大小 3，滑动窗口的最大值为 {4, 4, 6, 6, 6, 5}。

这类问题的挑战在于如何高效地找到滑动窗口中的最大值并随着窗口的移动进行更新，而不是每次移动窗口后重新计算。

❤️‍🔥解题思路

大顶堆法是解决滑动窗口最大值问题的一种高效方案。我们可以使用优先队列（大顶堆）来维护窗口内的最大值。

1. 使用大顶堆求解

大顶堆是一种数据结构，堆顶元素始终是堆中的最大元素。在 Java 中可以使用 PriorityQueue 实现大顶堆，通过传入比较器定义排序方式。以下是解决该问题的详细步骤：

初始化窗口内的元素：在 num 数组中，首先将前 size 个元素加入到大顶堆中。这样，堆顶元素就是当前窗口的最大值。
向右滑动窗口：从 size开始，逐步向右滑动窗口，维护堆内的元素。
- 删除窗口左侧离开的元素，即将堆中的最旧元素移除。
- 将窗口新加入的元素插入堆中。
- 堆顶元素即为当前窗口的最大值，将其加入结果数组中。
完成滑动过程：当窗口滑动到数组末尾时，结束循环。

2. 时间复杂度分析

假设数组的长度为 N，窗口大小为 M。在窗口滑动的过程中，每次添加或删除元素的时间复杂度为 O(log M)，因此总体时间复杂度为 O(N log M)。空间复杂度为 O(M)，用于存储滑动窗口内的元素。

💝代码实现

以下是该方法的 Java 代码：

import java.util.ArrayList;
import java.util.PriorityQueue;public class MaxInSlidingWindow {public ArrayList<Integer> maxInWindows(int[] num, int size) {ArrayList<Integer> ret = new ArrayList<>();if (size > num.length || size < 1)return ret;// 创建大顶堆PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);// 初始化第一个窗口的元素到堆中for (int i = 0; i < size; i++)heap.add(num[i]);// 记录第一个窗口的最大值ret.add(heap.peek());// 滑动窗口for (int i = 0, j = i + size; j < num.length; i++, j++) {heap.remove(num[i]);  // 移除窗口最左侧的元素heap.add(num[j]);      // 添加窗口右侧新元素ret.add(heap.peek());   // 堆顶元素为当前窗口的最大值}return ret;}
}

代码解释

PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);：定义了一个大顶堆。
heap.peek()：获取当前窗口的最大值。
在每次滑动时，通过 heap.remove() 删除旧元素，heap.add() 添加新元素，维护窗口最大值。