src/main/java/com/thealgorithms/datastructures/queues/SlidingWindowMaximum.java - master - NikolayIvkin/TheAlgorithms

src/main/java/com/thealgorithms/datastructures/queues/SlidingWindowMaximum.java

63 строки2 KB

Hardik Pawar

Add `SlidingWindowMaximum` algorithm (#5839)

26 окт 2024, 15:12

26 окт 2024, 15:1204e421b

package com.thealgorithms.datastructures.queues;

import java.util.Deque;
import java.util.LinkedList;

/**
 * The {@code SlidingWindowMaximum} class provides a method to efficiently compute
 * the maximum element within every sliding window of size {@code k} in a given array.
 *
 * <p>The algorithm uses a deque to maintain the indices of useful elements within
 * the current sliding window. The time complexity of this approach is O(n) since
 * each element is processed at most twice.
 *
 * @author Hardvan
 */
public final class SlidingWindowMaximum {
    private SlidingWindowMaximum() {
    }

    /**
     * Returns an array of the maximum values for each sliding window of size {@code k}.
     * <p>If {@code nums} has fewer elements than {@code k}, the result will be an empty array.
     * <p>Example:
     * <pre>
     * Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
     * Output: [3, 3, 5, 5, 6, 7]
     * </pre>
     *
     * @param nums the input array of integers
     * @param k the size of the sliding window
     * @return an array containing the maximum element for each sliding window
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n < k || k == 0) {
            return new int[0];
        }

        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // Remove elements from the front of the deque if they are out of the current window
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Remove elements from the back if they are smaller than the current element
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // Add the current element's index to the deque
            deque.offerLast(i);

            // Store the maximum element for the current window (starting from the k-1th element)
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }
}