A leaderboard that only keeps people who could still be champion: when a stronger player joins, weaker ones behind can never win and are removed.
Clues that point here
→ Maximum or minimum of every sliding window
→ DP where you need the max of the last k states
Not this pattern when
✕ The window is the whole array
✕ You need the median (two heaps)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Monotonic Deque · template
Deque<Integer> dq = new ArrayDeque<>(); // indexes, values decreasing
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); // left the window
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast(); // can never be max
dq.offerLast(i);
if (i >= k - 1) result[i - k + 1] = nums[dq.peekFirst()];
}
return result;