import java.util.*;

class Solution {
    // Function to return the max of each sliding window of size k
    public List<Integer> maxSlidingWindow(int[] nums, int k) {
        // Deque to store indices of useful elements
        Deque<Integer> dq = new LinkedList<>();

        // List to store result
        List<Integer> result = new ArrayList<>();

        // Loop through each element
        for (int i = 0; i < nums.length; i++) {
            // Remove indices out of current window
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }

            // Remove smaller values from the back of deque
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }

            // Add current index
            dq.offerLast(i);

            // Add to result once the first window is formed
            if (i >= k - 1) {
                result.add(nums[dq.peekFirst()]);
            }
        }

        // Return result list
        return result;
    }
}

// Driver code
public class Main {
    public static void main(String[] args) {
        Solution obj = new Solution();

        int[] arr = {4, 0, -1, 3, 5, 3, 6, 8};
        int k = 3;

        List<Integer> ans = obj.maxSlidingWindow(arr, k);

        for (int num : ans) {
            System.out.print(num + " ");
        }
    }
}

1234567891011121314151617181920212223242526272829303132333435363738394041424344

from collections import deque
from typing import List

class Solution:
    # Function to return the max of each sliding window of size k
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Deque to store indices of useful elements
        dq = deque()

        # Result list to store window maximums
        result = []

        # Loop through each element
        for i in range(len(nums)):
            # Remove indices that are out of the current window
            if dq and dq[0] <= i - k:
                dq.popleft()

            # Remove all elements from the back that are smaller than current element
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()

            # Add current index to deque
            dq.append(i)

            # Append max to result once the first window is completed
            if i >= k - 1:
                result.append(nums[dq[0]])

        # Return the result list
        return result

# Driver code
if __name__ == "__main__":
    obj = Solution()

    arr = [4, 0, -1, 3, 5, 3, 6, 8]
    k = 3

    ans = obj.maxSlidingWindow(arr, k)

    # Print the result
    print(*ans)

12345678910111213141516171819202122232425262728293031<