Задача: Максимальное скользящее

Условие: дан целочисленный массив, а также размер k подмассива, начинающегося от левой границы, и заканчивающегося в процессе выполнения алгоритма у правой границы. На каждом шаге можно просматривать k последовательных элементов скользящего массива. На каждом шаге надо определить максимальное значение скользящего.

Пример:

Ввод: nums = [1,3,-1,-3,5,3,6,7], k = 3

Вывод: [3,3,5,5,6,7]

Объяснение:

Скользящее на каждой итерации  Max

--------------------------  -----

[1 3 -1] -3 5 3 6 7    3

 1 [3 -1 -3] 5 3 6 7    3

 1 3 [-1 -3 5] 3 6 7     5

 1 3 -1 [-3 5 3] 6 7    5

 1 3 -1 -3 [5 3 6] 7    6

 1 3 -1 -3 5 [3 6 7]   7

Ввод: nums = [1], k = 1

Вывод: [1]

Решение:

Python

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        v = []  # Array to store the maximum value in each window starting at index 0
        va = []  # Array to store the maximum value in each window ending at the last index
        ans = []  # Array to store the final maximum values for each window
        max_val = nums[0]  # Initialize the maximum value to the first element
        a = 0  # Counter for the current window size

        # Iterate through the input array 'nums'
        for i in range(len(nums)):
            if a == k:
                max_val = nums[i]
                a = 0

            if max_val < nums[i]:
                max_val = nums[i]

            v.append(max_val)  # Store the maximum value in the current window
            a += 1

        a = 0
        max_val = float('-inf')
        b = len(nums) % k

        # Calculate the maximum values for windows ending at the last index
        for i in range(len(nums) - 1, len(nums) - 1 - b, -1):
            if max_val < nums[i]:
                max_val = nums[i]

            va.append(max_val)

        max_val = float('-inf')

        # Calculate the maximum values for the remaining windows
        for i in range(len(nums) - 1 - b, -1, -1):
            if a == k:
                max_val = nums[i]
                a = 0

            if max_val < nums[i]:
                max_val = nums[i]

            va.append(max_val)
            a += 1

        j = len(nums) - 1

        # Compare the maximum values from 'v' and 'va' for each window and store the maximum in 'ans'
        for i in range(k - 1, len(nums)):
            if v[i] > va[j]:
                ans.append(v[i])
            else:
                ans.append(va[j])

            j -= 1

        return ans  # Return the final maximum values for each window