Untitled

 avatar
unknown
plain_text
a month ago
1.3 kB
2
Indexable
public class SlidingWindowMaximum {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        int i = 0, j = 0;

        // Process the first k elements
        while (j < k) {
            // Remove smaller elements as they are not useful
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[j]) {
                deque.pollLast();
            }
            deque.addLast(j);
            j++;
        }
        // Store the maximum for the first window
        result[i++] = nums[deque.peekFirst()];

        // Process the rest of the elements
        while (j < n) {
            // Remove smaller elements as they are not useful
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[j]) {
                deque.pollLast();
            }
            deque.addLast(j);
           
            // Remove elements not in the current window
            if (!deque.isEmpty() && deque.peekFirst() < j - k + 1) {
                deque.pollFirst();
            }

            // Store the maximum for the current window
            result[i++] = nums[deque.peekFirst()];
            j++;
        }

        return result;
    }
}
Leave a Comment