@Test public void testLongList() { final int trials = 30000; for (int i = 0; i < trials; i++) { List<Long> list = new ArrayList<>(); int listLen = rand.nextInt(1000); for (int j = 0; j < listLen; j++) list.add((long)rand.nextInt(100)); int window = rand.nextInt(10) + 1; boolean maximize = rand.nextBoolean(); List<Long> expect = computeNaive(list, window, maximize); List<Long> actual = SlidingWindowMinMax.compute(list, window, maximize); Assert.assertEquals(expect, actual); } }
public static int[] compute(int[] array, int window, boolean maximize) { Objects.requireNonNull(array); if (window <= 0) throw new IllegalArgumentException("Window size must be positive"); if (array.length < window) return new int[0]; int[] result = new int[array.length - window + 1]; Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < array.length; i++) { int val = array[i]; while (!deque.isEmpty() && (!maximize && val < deque.getLast() || maximize && val > deque.getLast())) deque.removeLast(); deque.addLast(val); int j = i + 1 - window; if (j >= 0) { result[j] = deque.getFirst(); if (array[j] == result[j]) deque.removeFirst(); } } return result; }
SlidingWindowMinMax { public static int[] compute(int[] array, int window, boolean maximize) { Objects.requireNonNull(array); if (window <= 0) throw new IllegalArgumentException("Window size must be positive"); if (array.length < window) return new int[0]; int[] result = new int[array.length - window + 1]; Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < array.length; i++) { int val = array[i]; while (!deque.isEmpty() && (!maximize && val < deque.getLast() || maximize && val > deque.getLast())) deque.removeLast(); deque.addLast(val); int j = i + 1 - window; if (j >= 0) { result[j] = deque.getFirst(); if (array[j] == result[j]) deque.removeFirst(); } } return result; } }
SlidingWindowMinMax { public static int[] compute(int[] array, int window, boolean maximize) { Objects.requireNonNull(array); if (window <= 0) throw new IllegalArgumentException("Window size must be positive"); if (array.length < window) return new int[0]; int[] result = new int[array.length - window + 1]; Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < array.length; i++) { int val = array[i]; while (!deque.isEmpty() && (!maximize && val < deque.getLast() || maximize && val > deque.getLast())) deque.removeLast(); deque.addLast(val); int j = i + 1 - window; if (j >= 0) { result[j] = deque.getFirst(); if (array[j] == result[j]) deque.removeFirst(); } } return result; } SlidingWindowMinMax(); }
SlidingWindowMinMax { public static int[] compute(int[] array, int window, boolean maximize) { Objects.requireNonNull(array); if (window <= 0) throw new IllegalArgumentException("Window size must be positive"); if (array.length < window) return new int[0]; int[] result = new int[array.length - window + 1]; Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < array.length; i++) { int val = array[i]; while (!deque.isEmpty() && (!maximize && val < deque.getLast() || maximize && val > deque.getLast())) deque.removeLast(); deque.addLast(val); int j = i + 1 - window; if (j >= 0) { result[j] = deque.getFirst(); if (array[j] == result[j]) deque.removeFirst(); } } return result; } SlidingWindowMinMax(); static int[] compute(int[] array, int window, boolean maximize); static List<E> compute(List<E> list, int window, boolean maximize); E getMinimum(); E getMaximum(); void addTail(E val); void removeHead(E val); }
SlidingWindowMinMax { public static int[] compute(int[] array, int window, boolean maximize) { Objects.requireNonNull(array); if (window <= 0) throw new IllegalArgumentException("Window size must be positive"); if (array.length < window) return new int[0]; int[] result = new int[array.length - window + 1]; Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < array.length; i++) { int val = array[i]; while (!deque.isEmpty() && (!maximize && val < deque.getLast() || maximize && val > deque.getLast())) deque.removeLast(); deque.addLast(val); int j = i + 1 - window; if (j >= 0) { result[j] = deque.getFirst(); if (array[j] == result[j]) deque.removeFirst(); } } return result; } SlidingWindowMinMax(); static int[] compute(int[] array, int window, boolean maximize); static List<E> compute(List<E> list, int window, boolean maximize); E getMinimum(); E getMaximum(); void addTail(E val); void removeHead(E val);  }