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.
1#include <stdio.h>
2#include <limits.h>
3
4void maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize, int* result) {
5 *returnSize = numsSize - k + 1;
6 for (int i = 0; i <= numsSize - k; ++i) {
7 int max = INT_MIN;
8 for (int j = i; j < i + k; ++j) {
9 if (nums[j] > max) {
10 max = nums[j];
11 }
12 }
13 result[i] = max;
14 }
15}
16
17int main() {
18 int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
19 int k = 3;
20 int returnSize;
21 int result[6];
22 maxSlidingWindow(nums, 8, k, &returnSize, result);
23 for (int i = 0; i < returnSize; ++i) {
24 printf("%d ", result[i]);
25 }
26 return 0;
27}This C solution iteratively evaluates each window by checking each element individually to find the maximum. It requires nested loops where one iterates through each window starting point and the other iterates within the window to find the maximum.
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 JavaScript solution utilizes an array as a deque to maintain indices of relevant elements. The maximum element in a window is efficiently accessed using array operations to ensure correctness and performance.