当前位置: 首页 > article >正文

LeetCode hot 100—滑动窗口最大值

题目

给你一个整数数组 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]

分析

双端队列法

双端队列是一种可以在两端进行插入和删除操作的线性数据结构。可以在 O(1) 的时间复杂度内完成队首和队尾元素的插入和删除操作,从而使得我们能够高效地维护滑动窗口内的最大值。

整体思路

对于每个元素 nums[i]

  • 移除窗口外的元素:如果队列的队首元素 window.front() 等于 i - k,说明该元素已经不在当前滑动窗口内,将其从队列中移除。
  • 保持队列递减:从队列的队尾开始,移除所有小于当前元素 nums[i] 的元素。因为这些元素不可能是后续滑动窗口中的最大值,所以可以直接移除。
  • 将当前元素的索引加入队列:将当前元素的索引 i 加入队列的队尾。
  • 记录最大值:当 i 大于等于 k - 1 时,说明滑动窗口的大小已经达到 k,此时队列的队首元素对应的元素就是当前滑动窗口中的最大值,将其加入 result 中。

时间复杂度:O(n)

空间复杂度:O(k)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        std::vector<int> result;
        std::deque<int> window;
        for (int i = 0; i < nums.size(); ++i) {
            // 移除窗口外的元素
            if (!window.empty() && window.front() == i - k) {
                window.pop_front();
            }
            // 保持队列递减,移除小于当前元素的元素
            while (!window.empty() && nums[window.back()] < nums[i]) {
                window.pop_back();
            }
            // 将当前元素的索引加入队列
            window.push_back(i);
            // 当窗口大小达到 k 时,记录最大值
            if (i >= k - 1) {
                result.push_back(nums[window.front()]);
            }
        }
        return result;
    }
};    

知识充电

deque 容器

初始化

#include <deque>
#include <iostream>

int main() {
    // 默认构造函数,创建一个空的双端队列
    std::deque<int> d1;

    // 构造一个包含 n 个值为 value 的元素的双端队列
    std::deque<int> d2(5, 10);  // 包含 5 个值为 10 的元素

    // 从另一个双端队列复制元素
    std::deque<int> d3(d2);

    // 从迭代器范围 [first, last) 复制元素
    std::deque<int> d4(d2.begin(), d2.end());

    return 0;
}

随机访问

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d = {1, 2, 3, 4, 5};

    // 通过下标访问元素
    std::cout << d[2] << std::endl;  // 输出 3

    // 通过 at() 方法访问元素,会进行边界检查,越界时抛出异常
    std::cout << d.at(3) << std::endl;  // 输出 4

    // 访问第一个元素
    std::cout << d.front() << std::endl;  // 输出 1

    // 访问最后一个元素
    std::cout << d.back() << std::endl;  // 输出 5

    return 0;
}

插入和删除

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d = {1, 2, 3};

    // 在尾部插入元素
    d.push_back(4);  // d 变为 {1, 2, 3, 4}

    // 在头部插入元素
    d.push_front(0);  // d 变为 {0, 1, 2, 3, 4}

    // 删除尾部元素
    d.pop_back();  // d 变为 {0, 1, 2, 3}

    // 删除头部元素
    d.pop_front();  // d 变为 {1, 2, 3}

    return 0;
}

当需要在队列的两端频繁进行插入和删除操作时,std::deque 是一个很好的选择,比如实现滑动窗口算法,就可以利用其在两端高效操作的特性来维护窗口内的元素。

当需要随机访问元素,但又不想像 std::vector 那样在头部插入或删除元素时性能不佳的情况,也可以使用 std::deque


http://www.kler.cn/a/585744.html

相关文章:

  • win32汇编环境,对话框程序中创建托盘示例一
  • PyTorch 系列教程:探索自然语言处理应用
  • 基于RWA 与 AI-Agent 协同的企业数字化生态构建
  • Go语言环境搭建并执行第一个Go程序
  • X86 RouterOS 7.18 设置笔记十:上海电信IPTV使用msd_lite实现组播转单拨
  • C++小课堂——friend友元
  • 基础知识《DICT协议》
  • 路由器配置命令
  • 完善机器人:让 DeepSeek 生成 API 接口,并在网页上调用
  • MySQL 的 innodb_buffer_pool_size 参数配置指南
  • [AI QA] strace | 探索 a.out
  • 正则表达式 - 修饰符
  • 书籍品读:我的世界(陈州)
  • C语言实现括号匹配检查及栈的应用详解
  • 【综述】An Introduction to Vision-Language Modeling【二】
  • 【linux驱动开发】创建proc文件系统中的目录和文件实现
  • Python 中 lambda 表达式、推导式和其他函数用法对比
  • QT中读取QSetting文件
  • Ubuntu 访问 Windows 共享文件夹
  • vue2升级Vue3--native、对inheritAttrs作用做以解释、声明的prop属性和未声明prop的属性