算法的学习笔记—滑动窗口的最大值(牛客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() 添加新元素，维护窗口最大值。

代码优化建议

大顶堆的实现适合窗口大小较小、元素数量适中的情况。在窗口较大或数据量较多的情况下，也可以使用双端队列来提高效率。双端队列的解法可以将时间复杂度降低到 O(N)，适合更大规模的数据。

????总结

滑动窗口最大值问题在算法题中具有较高的实用性和典型性。掌握使用大顶堆解决该问题的方法，对于理解和应用优先队列以及堆数据结构有很大帮助。希望本文的分析和代码示例可以帮助大家更好地理解该问题，并在未来的算法学习中加以应用。

????热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

????欢迎大家加入我的社区尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论????
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读????
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力????

秒客网