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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] MaxSlidingWindow(int[] nums, int k) {
6 List<int> result = new List<int>();
7 for (int i = 0; i <= nums.Length - k; i++) {
8 int max = Int32.MinValue;
9 for (int j = i; j < i + k; j++) {
10 max = Math.Max(max, nums[j]);
11 }
12 result.Add(max);
13 }
14 return result.ToArray();
15 }
16
17 public static void Main(string[] args) {
18 int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
19 int k = 3;
20 Solution s = new Solution();
21 int[] result = s.MaxSlidingWindow(nums, k);
22 Console.WriteLine(string.Join(" ", result));
23 }
24}This C# solution employs the same brute-force approach, iterating through elements and calculating the maximum for each window and collecting outcomes in a List
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
The Python solution uses collections.deque to efficiently maintain indices of elements. The deque is manipulated to ensure operations for determining the maximum and maintaining validity happen in constant time.