Skip to content

Instantly share code, notes, and snippets.

@kanrourou
Created January 27, 2015 22:17
class MyClass {
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment