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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5 public int[] maxSlidingWindow(int[] nums, int k) {
6 List<Integer> list = new ArrayList<>();
7 for (int i = 0; i <= nums.length - k; i++) {
8 int max = Integer.MIN_VALUE;
9 for (int j = i; j < i + k; j++) {
10 max = Math.max(max, nums[j]);
11 }
12 list.add(max);
13 }
14 return list.stream().mapToInt(i -> i).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 solution = new Solution();
21 int[] result = solution.maxSlidingWindow(nums, k);
22 for (int num : result) {
23 System.out.print(num + " ");
24 }
25 }
26}The Java solution iterates through potential window starting points and computes the maximum for each subarray, storing results in a list and then converting it to an array of integers.
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.
1using System.Collections.Generic;
public class Solution {
public int[] MaxSlidingWindow(int[] nums, int k) {
LinkedList<int> deq = new LinkedList<int>();
List<int> result = new List<int>();
for (int i = 0; i < nums.Length; i++) {
if (deq.Count > 0 && deq.First.Value <= i - k) {
deq.RemoveFirst();
}
while (deq.Count > 0 && nums[deq.Last.Value] < nums[i]) {
deq.RemoveLast();
}
deq.AddLast(i);
if (i >= k - 1) {
result.Add(nums[deq.First.Value]);
}
}
return result.ToArray();
}
public static void Main(string[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
Solution s = new Solution();
int[] result = s.MaxSlidingWindow(nums, k);
Console.WriteLine(string.Join(" ", result));
}
}For C#, a LinkedList is used as a deque to store indices of elements from the array. The deque is manipulated such that it efficiently provides the maximum element for any given sliding window using list operations.