import java.util.ArrayList;import java.util.Arrays;import java.util.Deque;import java.util.List;import java.util.concurrent.LinkedBlockingDeque;/** * 有一个×××数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右滑动一个位置。 * 返回一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值。 * * 例： * 数组arr=[4,3,5,4,3,3,6,7] w=3，结果为[5,5,5,4,6,7] * * 常规解连续比较w内的最大数，O(N*w) * * 最优解O(N) * @author Administrator * */public class CompareArray { /** * 双端队列存放着数组的下标值 */ private static Deque qmax = new LinkedBlockingDeque(); public static List dowork(int[] arr,int size) { List l = new ArrayList(); for(int i = 0,len = arr.length;i=size-1) { l.add(arr[qmax.peekLast()]); } } return l; } public static void main(String[] args) { int[] i = {4,3,5,4,3,3,6,7}; System.out.println(dowork(i,5)); }}
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/4418/viewspace-2813928/ ，如需转载，请注明出处，否则将追究法律责任。
请登录后发表评论
登录
全部评论
