Created
January 27, 2015 22:17
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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