国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > php教程 > 滑动窗口的最大值

滑动窗口的最大值

来源:程序员人生   发布时间:2016-07-26 13:14:53 阅读次数:700次

题目

给定1个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。
例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那末1共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个:
{[2,3,4],2,6,2,5,1},
{2,[3,4,2],6,2,5,1},
{2,3,[4,2,6],2,5,1},
{2,3,4,[2,6,2],5,1},
{2,3,4,2,[6,2,5],1},
{2,3,4,2,6,[2,5,1]}。

解题

方法1:暴力
时间复杂度:O(nk)

import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> result = new ArrayList<Integer>(); int len = num.length; if(size<=0 || size> len) return result; for(int i=0;i<len;i++){ int max = Integer.MIN_VALUE; for(int k=0;k+i < len && k<size;k++){ max = max>num[i+k]?max:num[i+k]; } result.add(max); if(i+size==len) break; } return result; } }

方法2:利用队列
队列寄存滑动窗口中较大元素的下标

import java.util.ArrayList; import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int[] num, int size) { ArrayList<Integer> result = new ArrayList<>(); if (num == null) { return result; } if (num.length < size || size < 1) { return result; } LinkedList<Integer> indexDeque = new LinkedList<>(); for (int i = 0; i < size; i++) { while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) { indexDeque.removeLast(); } indexDeque.addLast(i); } for (int i = size; i < num.length ; i++) { result.add(num[indexDeque.getFirst()]); while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) { indexDeque.removeLast(); } if (!indexDeque.isEmpty() && indexDeque.getFirst() <= (i - size)) { indexDeque.removeFirst(); } indexDeque.addLast(i); } result.add(num[indexDeque.getFirst()]); return result; } }

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生