一步步教会你怎么做网站,永康电子商务网站建设,国外域名绑定国内服务器,数码类网站名称#x1f4df;作者主页#xff1a;慢热的陕西人 #x1f334;专栏链接#xff1a;力扣刷题日记 #x1f4e3;欢迎各位大佬#x1f44d;点赞#x1f525;关注#x1f693;收藏#xff0c;#x1f349;留言 文章目录 牛客热题#xff1a;滑动窗口的最大值题目链接方法一… 作者主页慢热的陕西人 专栏链接力扣刷题日记 欢迎各位大佬点赞关注收藏留言 文章目录 牛客热题滑动窗口的最大值题目链接方法一暴力思路代码复杂度 方法二单调双端队列思路代码复杂度 牛客热题滑动窗口的最大值
题目链接
滑动窗口的最大值_牛客题霸_牛客网 (nowcoder.com)
方法一暴力
思路
枚举每个区间的起始 然后遍历每个区间获取最大值放入到ret中
代码
vectorint maxInWindows(vectorint num, int size) {int n num.size();vectorint ret;if(size 0 || size n) return ret;for(int i 0 ; i size - 1 n; i){int max_val -10010;for(int j 0; j size; j){max_val max(max_val, num[i j]);}ret.push_back(max_val);}return ret;}复杂度 时间复杂度O(N * M) ,其中N是数组的长度M为size的大小 空间复杂度O(N), 使用了一个N - size长度的数组用来返回答案 方法二单调双端队列
思路
step1对于数组长度为0窗口长度为0或者窗口长度超过num的直接返回空数组 step2遍历数组维护单调队列将队列尾部小于当前数组元素的值全部出队。step3将当前值入队尾部step4判断当前对头的下标是否超过区间长度的限制如果超过则出队头step5当前遍历的数组下标大于等于区间的长度那么则将对头放入到答案数组 step6遍历结束返回答案数组即可
代码 vectorint maxInWindows(vectorint num, int size) {int n num.size();vectorint ret; dequeint dp;if(n 0 || size 0 || size n) return ret;for(int i 0; i n; i){//除去队列中比当前值小的值while(!dp.empty() num[dp.back()] num[i])dp.pop_back();//将当前下标入队列dp.push_back(i);//判断队列头部的下标是否超过序列长度if(i - dp.front() size)dp.pop_front();//将最大值放入到答案中if(i 1 size)ret.push_back(num[dp.front()]);}return ret;}复杂度 时间复杂度O(N), 遍历了一遍数组求出了所有滑动窗口的最大值 空间复杂度O(N)其中开辟了N - size大小的答案数组和最大为size长度的双端队列
