Sponsored
Sponsored
This approach involves checking each possible window (of length k) one by one and calculating the maximum for each window. This method is straightforward but inefficient for large arrays as it runs in O(n*k) time complexity.
Time complexity: O(n*k), where n is the number of elements.
Space complexity: O(1) for storing the maximum of each window in output array.
1def maxSlidingWindow(nums, k):
2 result = []
3 for i in range(len(nums) - k + 1):
4 result.append(max(nums[i:i+k]))
5 return result
6
7# Example usage:
8nums = [1, 3, -1, -3, 5, 3, 6, 7]
9k = 3
10print(maxSlidingWindow(nums, k))In the Python solution, we use a list comprehension to evaluate each window, compute the maximum, and append to the result list, making use of the built-in max function.
Use a deque (double-ended queue) to store indices of array elements, which helps in maintaining the maximum for the sliding window in an efficient manner. As the window slides, the method checks and rearranges the deque so that the front always contains the index of the maximum element.
Time complexity: O(n), where n is the number of elements.
Space complexity: O(k) for the deque.
1
This C program uses a circular array-based deque to store indices. The deque is created such that the maximum element's index is always at the front and other elements are stored in a way that elements outside the window or smaller than the current maximum are removed efficiently.