This solution uses TreeMap, which comes handy in all sort of problems.
The code is way more compact and easy to understand.
import java.util.*;
public class MaximumInSlidingWindow {
public static List<Integer> findMaxSlidingWindow(List<Integer> nums, int windowSize) {
List<Integer> result = new ArrayList<>();
TreeMap<Integer, Integer> tm = new TreeMap<>((a, b)-> b.compareTo(a));
Deque<Integer> cache = new LinkedList<>();
for(int end = 0, start = 0; end < nums.size(); end++) {
tm.put(nums.get(end), tm.getOrDefault(nums.get(end), 0) + 1);
cache.add(nums.get(end));
if (end - start + 1 >= windowSize) {
result.add(tm.firstKey());
int first = cache.poll();
tm.put(first, tm.get(first) - 1);
if (tm.get(first) == 0) {
tm.remove(first);
}
start++;
} else if (windowSize > nums.size() && end == nums.size() - 1) {
result.add(tm.pollFirstEntry().getKey());
}
}
return result;
}
public static void main(String[] args) {
assert Arrays.deepEquals(findMaxSlidingWindow(Arrays.asList(-4, 5, 4, -4, 4, 6, 7), 2).toArray(), new Integer[]{5, 5, 4, 4, 6, 7});
assert Arrays.deepEquals(findMaxSlidingWindow(Arrays.asList(-4, 5, 4, -4, 4 , 6, 7), 10).toArray(), new Integer[]{7});
assert Arrays.deepEquals(findMaxSlidingWindow(Arrays.asList(3, 3, 3, 3, 3, 3), 3).toArray(), new Integer[]{3, 3, 3, 3});
assert Arrays.deepEquals(findMaxSlidingWindow(Arrays.asList(1, 2, 3, 1, 4, 5, 2, 3, 6), 3).toArray(), new Integer[]{3, 3, 4, 5, 5, 5, 6});
}
}
Even though the method in TreeMap is called remove, in this case the time complexity is log(n), much better than n which we would have with a PriorityQueue.
Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Find Maximum in Sliding Window - Grokking Coding Interview Patterns in Java