Lintcode: Sliding Window Maximum

Solution 1: 用heap保存对。虽然能通过OJ，但是复杂度并不对

public class Solution {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
    	if (nums == null || nums.length == 0 || k <= 0) {
    		return res;
    	}
    	PriorityQueue<Pair> heap = new PriorityQueue<Pair>();
    	for (int i = 0; i < k; i++) {
    		heap.add(new Pair(nums[i], i));
    		//res.add(heap.peek().val);
    	}
    	for (int i = k; i < nums.length; i++) {
    	    res.add(heap.peek().val);
    		Pair toRemove = heap.peek();
    		while (!heap.isEmpty() && heap.peek().index <= i - k) {
    			heap.remove();
    		}
    		heap.add(new Pair(nums[i], i));
    	}
    	res.add(heap.peek().val);
    	return res;
    }
    class Pair implements Comparable<Pair> {
    	int val;
    	int index;
    	public Pair(int val, int index) {
    		this.val = val;
    		this.index = index;
    	}
    	@Override
		public int compareTo(Pair p) {
			return Integer.compare(p.val, val);
		}
    }
}

Solution 2: 用double end queue– Deque.将当前元素加在queue的最后，但是加之前把所有比当前值小的元素从后往前删掉，这样就保证了一个按照index顺序维护的降序queue。非常好的思路。

public class Solution {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
    	if (nums == null || nums.length == 0 || k <= 0) {
    		return res;
    	}
    	Deque<Integer> dQueue = new LinkedList<Integer>();
    	for (int i = 0; i < k; i++) {
    		while (!dQueue.isEmpty() && nums[dQueue.peekLast()] <= nums[i]) {
    			dQueue.removeLast();
    		}
    		dQueue.addLast(i);
    	}
    	for (int i = k; i < nums.length; i++) {
    	    res.add(nums[dQueue.peekFirst()]);
    		while (!dQueue.isEmpty() && dQueue.peek() <= i - k) {
    			dQueue.removeFirst();
    		}
    		while (!dQueue.isEmpty() && nums[dQueue.peekLast()] <= nums[i]) {
    			dQueue.removeLast();
    		}
    		dQueue.addLast(i);
    	}
    	res.add(nums[dQueue.peekFirst()]);
    	return res;
    }
}

Lintcode: Median II

Numbers keep coming, return the median of numbers at every time a new number added.
Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n-1)/2].
用到了heap，i.e. Java里是priorityqueue，平时很少用到，需要练习。

public class Solution {
    public int[] medianII(int[] nums) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        class maxComparator implements Comparator<Integer> {
            public int compare(Integer a, Integer b) {
                return Integer.compare(b, a);
            }
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(nums.length, new maxComparator());
        int[] result = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            if (minHeap.size() < maxHeap.size()) {
                if (nums[i] < maxHeap.peek()) {
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(nums[i]);
                } else {
                    minHeap.offer(nums[i]);
                }
            } else {
                if (minHeap.size() > 0 && nums[i] > minHeap.peek()) {
                    maxHeap.offer(minHeap.poll());
                    minHeap.offer(nums[i]);
                } else {
                    maxHeap.offer(nums[i]);
                }
            }
            result[i] = maxHeap.peek();
        }
        return result;
    }
}