public static void main(String[] args) {

int nums[] = {-95,92,-85,59,-59,-14,88,-39,2,92,94,79,78,-58,37,48,63,-91,91,74,-28,39,90,-9,-72,-88,-72,93,38,14,-83,-2,21,4,-75,-65,3,63,100,59,-48,43,35,-49,48,-36,-64,-13,-7,-29,87,34,56,-39,-5,-27,-28,10,-57,100,-43,-98,19,-59,78,-28,-91,67,41,-64,76,5,-58,-89,83,26,-7,-82,-32,-76,86,52,-6,84,20,51,-86,26,46,35,-23,30,-51,54,19,30,27,80,45,22};

int k = 10;

int[] res = maxSlidingWindow(nums,k);

for (int i = 0; i < res.length ; i++) {

System.out.print(res[i]);

System.out.print(',');

}

}

public static int[] maxSlidingWindow(int[] nums, int k) {

if(nums.length==0)

return new int[]{};

int[] res = new int[nums.length-k+1];

int cur = 0;

Deque<Integer> dq = new LinkedList(); //队列里是递减的，存的仍然是下标

for (int i = 0; i < nums.length ; i++) {

if( !dq.isEmpty() && dq.peekFirst()<=i-k) //窗口长度过长了，删掉头

dq.removeFirst();

while( !dq.isEmpty() && nums[dq.peekLast()]<=nums[i]){// removeLast 不是 First。 自己写的时候这写错了，如果是First的话，有些Case也能过

dq.removeLast();

}

dq.addLast(i);

if(i>=k-1){

res[cur] = nums[dq.peekFirst()];

cur++;

}

}

return res;

}