Sliding Window Maximum

1package pkg5leetcode.top100;2 3/*4 * Sliding Window Maximum | LC 2395 * APPROACH: Monotonic deque stores indices of decreasing values.6 * COMPLEXITY: Time O(n), Space O(k)7 */8import java.util.*;9 10public class top100_LC239SlidingWindowMaximum {11    static int[] maxSlidingWindow(int[] nums, int k) {12        Deque<Integer> dq = new ArrayDeque<>();13        int[] res = new int[nums.length - k + 1];14        for (int i = 0; i < nums.length; i++) {15            while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();16            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();17            dq.offerLast(i);18            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];19        }20        return res;21    }22 23    public static void main(String[] args) {24        check(java.util.Arrays.equals(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3),25            new int[]{3, 3, 5, 5, 6, 7}), "case1");26        check(java.util.Arrays.equals(maxSlidingWindow(new int[]{1}, 1), new int[]{1}), "case2");27        System.out.println("all tests passed");28    }29 30    static void check(boolean cond, String name) {31        if (!cond) throw new AssertionError("FAILED: " + name);32        System.out.println("  PASS " + name);33    }34}