単調キュー-長さkの窓で整数数列を移動し、窓に含まれる数の最大値を求める

import java.util.LinkedList;

/*

         
            ：           ，       

  ：       N     a(i),i=0,1,...,N-1    k.

  ：f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1

                k          ，             

    
@    http://weibo.com/lirenchen
http://weibo.com/1915548291/z3T4HbRRr 
          ：
@  RickyYang：     k      ，           ，         ，      ，
        ，           ，      ，        ，     。         nlogk,  n-k+logk (11 6  08:22)

        。              。        ：“        ，           ，      ，        ”
    ，                 ，  “      ”，         

         ：
http://xuyemin520.is-programmer.com/posts/25964

1.       ：          ，       v   ，        v  ，
          v,        ，             v  ，         v,        v     

2.           ，              ？
         i  k-1        ，                 i-k+1   ，
           f(i)       ，           。   index[    ]<i-k+1 ，        

        ，     ，     LinkedList，                     。             ^_^

*/
public class SlidingWindow {

	public static void main(String[] args) {
		/*
		int[] array = { 8, 7, 12, 5, 16, 9, 17, 2, 4, 6 };
		int k = 3;
		 */
		
		int[] array = { 3, 4, 5, 7, 3, 5, 2, 9 };
		int k = 3;
		
		int[] max = maxInWindow(array, k);
		for (int i : max) {
			System.out.println(i);
		}
	}

	public static int[] maxInWindow(int[] array, int k) {
		if (k <= 0 || array == null || array.length == 0) {
			System.out.println("invalid input");
			return new int[0];
		}
		int len = array.length;
		int[] max = new int[len];
		if (k == 1) {
			System.arraycopy(array, 0, max, 0, len);	//    ，      
		} else {
			LinkedList<Item> queue = new LinkedList<Item>();
			for (int i = 0; i < len; i++) {
				Item curItem = new Item(array[i], i);
				if (queue.isEmpty()) {
					queue.addLast(curItem);
				} else {
					Item head = queue.getFirst();
					int headIndex = head.getIndex();
					
					//            ，   
					if (headIndex < (i - k + 1)) {	
						queue.removeFirst();
					}
					
					//    
					while (!queue.isEmpty()) {
						Item tail = queue.getLast();
						int tailValue = tail.getValue();
						if (tailValue < array[i]) {
							queue.removeLast();
							if (queue.isEmpty()) {
								queue.addLast(curItem);
								break;
							}
						} else if (tailValue > array[i]) {
							queue.addLast(curItem);
						} else {
							break;
						}
					}
				}
				
				//     ，             
				if (!queue.isEmpty()) {
					max[i] = queue.getFirst().getValue();
				}
			}
		}
		return max;
	}

}

class Item {
	
	//     
	private int value;
	
	//         
	private int index;

	public Item(int value, int index) {
		this.value = value;
		this.index = index;
	}

	public int getValue() {
		return value;
	}

	public int getIndex() {
		return index;
	}

}