小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

Leetcode题目解析(191105)

2019年11月6日 743点热度 0人点赞 0条评论

Leetcode 239:滑动窗口最大值

题目描述

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

示例

输入: 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

解题思路

在剑指offer题目解析(2)中也曾经有这个题,我当时使用的是模拟建立一个滑动窗口,因为该方法使用了两个for循环,所以复杂度为O(n2),这个版本在leetcode中是无法通过的。但是现在有一种新的方法可以保证算法整体时间复杂度为O(n)。

借鉴这里,实际我们并不需要每次都提取3个元素进行比较,因为实际每一次比较的3个元素,都有两个元素与前面的两个元素是重叠的(即是前一组元素减掉最前面的值),这个时候我们可以考虑采用类似于队列的方法。即需要写:

void push(int n);//在队尾插入一个元素
void pop(int n);//队头元素如果是n删除它
int max();//返回当前队列中的最大值

根据这个思想,写出主体框架来:

 vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> result;
        if (nums.empty())
            return result;
        Solution win;
        for (int i = 0; i < nums.size(); i++)
        {
            if (i < k - 1)
                win.push(nums[i]);//先填满窗口前k-1个元素
            else {
            //插入队尾元素,else后面这三句话相当于窗口滑动且找到最大值push给result
                win.push(nums[i]);
                result.push_back(win.max());
                win.pop(nums[i - k + 1]);
            }
        }
        return result;
    }

结构

接下来我们要实现各个函数的功能。

对于push来说,我们依然要在队尾添加元素,但是要把前面比新元素小的元素都删除掉。这样的话,最终单调队列中的元素就会保持一个单调递减的顺序。所以push和max都可以直接这样写:

void push(int n) {
        while (!data.empty() && data.back() < n) 
            data.pop_back();
        data.push_back(n);
    }

int max() {
    return data.front();
}

代码实现

class Solution {
public:
    private:
    deque<int> deq;
public:
    void push(int k)
    {
        while (!deq.empty() && deq.back() < k)
            deq.pop_back();
        deq.push_back(k);
    }

    int max() { return deq.front(); }

    void pop(int k)
    {
        if (!deq.empty() && deq.front() == k)
            deq.pop_front();
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> result;
        if (nums.empty())
            return result;
        Solution win;
        for (int i = 0; i < nums.size(); i++)
        {
            if (i < k - 1)
                win.push(nums[i]);//先填满窗口前k-1个元素
            else {
                win.push(nums[i]);
                result.push_back(win.max());
                win.pop(nums[i - k + 1]);
            }
        }
        return result;
    }
};

复杂度

复杂度配图

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年11月6日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
生日快乐,我15岁咯! 小奥的专属天地V2正式上线! 《实时语音处理实践指南》学习笔记:第一章 每日一评0823:现代青少年的“早熟”与“晚熟” 现在、新的已经开始 再回陈毅中学
标签聚合
leetcode 学习 python学习 生活 Java 算法 鸟哥的linux私房菜 高中 linux Python
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号