今�Hの国の呵呵君: [Algorithm]Maximum and Minimum in Window of Numbers

今�Hの国の呵呵君: [Algorithm]Maximum and Minimum in Window of Numbers

Given an array of integer elements and an integer d please consider all the sequences of dconsecutive elements in the array. For each sequence we compute the difference between the maximum and the minimum value of the elements in that sequence and name it the deviation.

Your task is to

• write a function that computes the maximum value among the deviations of all the sequences considered above
• print the value the standard output (stdout) 

本质上是窗口最大最小值的问题，我们很自然的先想到应该用heap，时间复杂度是O(n log n)，这是显而易见的解法。但实际上，这一题我们可以到达O(n)的时间复杂度，我们用双向队列，以窗口最大值为例，假设窗口大小为k，队列的最大size是k，我们队列里维护的从头到尾是从旧到新，并且是严格递减序列，来了一个新值的话，我们做以下操作：

• 如果队尾元素小于等于当前元素，我们一直dequeue直到队列或者队尾元素大于当前元素，然后从队尾入队
• 如果对头元素在窗口范围外了，将队头元素出队

我们会在两端出队，在队尾入队，窗口最小值的话是类似的。每个元素最多入队一次出队一次，时间复杂度O(n)，代码如下：

	public static void find_deviation(Integer[] v, Integer d) { // Write your code here
	// To print results to the standard output you can use System.out.println()
	// Example: System.out.println("Hello world!");
	if (v == null)
	return;
	int len = v.length, maxDev = 0;
	//max size d, store indexes of elememts in decreasing order
	LinkedList<Integer> maxQueue = new LinkedList<Integer>();
	//max size d, stroe indexes of elements in increasing order
	LinkedList<Integer> minQueue = new LinkedList<Integer>();
	//for each consecutive region
	for (int i = 0; i < len; i++) {
	//gurantee decreasing order
	while(!maxQueue.isEmpty() && v[maxQueue.getLast()] <= v[i])
	maxQueue.removeLast();
	//gurantee decreasing order
	while (!minQueue.isEmpty() && v[minQueue.getLast()] >= v[i])
	minQueue.removeLast();
	//remove first element in queue if it is out of range
	if (!maxQueue.isEmpty() && maxQueue.getFirst() < i - d + 1)
	maxQueue.removeFirst();
	if (!minQueue.isEmpty() && minQueue.getFirst() < i - d + 1)
	minQueue.removeFirst();
	maxQueue.addLast(i);
	minQueue.addLast(i);
	if (i >= d) {
	int dev = v[maxQueue.getFirst()] - v[minQueue.getFirst()];
	maxDev = dev > maxDev? dev: maxDev;
	}
	}
	System.out.println(maxDev);
	}

Read full article from 今�Hの国の呵呵君: [Algorithm]Maximum and Minimum in Window of Numbers