Leetcode 239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[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

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:  You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up: Could you solve it in linear time?

用一个滑窗在数组上滑动,求滑动到每个位置时,滑窗内数字的最大值,线性时间内完成。

使用双端队列完成,队列记录数组中的下标,维护多个单调递减区间。

当当前下标和队列首的元素相差超过k-1时,说明滑窗超过了既定大小,需要把前一个元素扔掉。

因为要维护单调递增,所以每次加入一个新的下标时,需要将新加入的数和队列尾的数字比较,扔掉比新加入的数小的数,因为它们不可能是滑窗内的最大值。

当下标大于等于k-1的时候,说明要开始记录滑窗的最大值了。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for(int i = 0; i < nums.size(); i++)
        {
            if(!q.empty() && i - q.front() >= k) q.pop_front();
            while(!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            if(i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 97 Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. ...

21110
来自专栏IT 指南者专栏

Python 从入门到入门基础练习十五题

微信公众号:compassblog 欢迎关注、转发,互相学习,共同进步! 有任何问题,请后台留言联系! ? 1、永远的 HelloWorld print("He...

8617
来自专栏程序生活

Python json 模块dumps、dump、loads、load的使用

本文主要讲下json.dumps和json.dump、json.loads和json.load的区别,因为经常需要加载json文件,读取数据,傻傻分不清...

681
来自专栏desperate633

LintCode 哈希函数题目代码

在数据结构中,哈希函数是用来将一个字符串(或任何其他类型)转化为小于哈希表大小且大于等于零的整数。一个好的哈希函数可以尽可能少地产生冲突。一种广泛使用的哈希函数...

994
来自专栏小樱的经验随笔

ECJTUACM16 Winter vacation training #4 题解&源码

https://vjudge.net/contest/149692#overview 这周一VJ比赛,题解&源码已完成! A.....................

38511
来自专栏数据结构与算法

2806 红与黑 个人博客:doubleq.win

个人博客:doubleq.win 2806 红与黑  时间限制: 1 s  空间限制: 64000 KB  题目等级 : 白银 Silver 题解  查看运行结...

2854
来自专栏Duncan's Blog

Hive SQL 学习

example: 一个班有学生id,成绩,班级,现在将学生根据班级按照成绩排名。(partition by)

2682
来自专栏数说工作室

【SAS Says】基础篇:描述性分析(下)

好吧,这一节是留给处女座的,主要说如何用proc tabulate和proc report产生一个更加耐看的报告。有时候print、means和freq产生的报...

5045
来自专栏后端技术探索

(答案来了)两道腾讯面试题目

前天推送的文章《两道腾讯技术面试题(二面经历)》,收到了不少留言,感兴趣的可以去哪篇文章下查看精选留言,有一多半同学没有正确理解题目,可分享的留言寥寥无几,根据...

1041
来自专栏从流域到海域

Python reduce()函数

MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean and Sanj...

1959

扫码关注云+社区