Algorithm
Problem Name: 239. Sliding Window Maximum
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position 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
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int getmax(int *nums, int k) {
int i;
int max = nums[0];
for (i = 1; i < k; i ++) {
if (max < nums[i]) max = nums[i];
}
return max;
}
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
int max = 0, i;
int *buff;
if (!numsSize) return NULL;
*returnSize = numsSize - k + 1;
buff = malloc((*returnSize) * sizeof(int));
//assert(buff);
buff[0] = getmax(&nums[0], k);
for (i = 1; i + k < = numsSize; i ++) {
if (buff[i - 1] < nums[i + k - 1]) {
buff[i] = nums[i + k - 1];
} else if (buff[i - 1] == nums[i - 1]) {
buff[i] = getmax(&nums[i], k);
} else {
buff[i] = buff[i - 1];
}
}
return buff;
}
Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3,3,5,5,6,7]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int>res;
if (nums.size() == 0) return res;
int start = 0;
int end = k - 1;
int maxIndex = findMax(nums, start, end);
for (; end < nums.size(); start++, end++) {
if (nums[end] > nums[maxIndex]) maxIndex = end;
if (start > maxIndex) maxIndex = findMax(nums, start, end);
res.push_back(nums[maxIndex]);
}
return res;
}
int findMax(vector<int>& nums, int start, int end) {
int maxIndex = start;
for (int i = start + 1; i < = end; i++)
if (nums[i] > nums[maxIndex]) maxIndex = i;
return maxIndex;
}
};
Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3,3,5,5,6,7]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) {
return new int[0];
}
int[] result = new int[n - k + 1];
Deque < Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (deque.size() > 0 && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
while (deque.size() > 0 && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i -k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}
Input
nums = [1], k = 1
Output
[1]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const maxSlidingWindow = function(nums, k) {
const n = nums.length
const stk = []
const res = []
for(let i = 0; i < n; i++) {
while(stk.length && stk[0] < i - k + 1) {
stk.shift()
}
while(stk.length && nums[stk[stk.length - 1]] <= nums[i]) {
stk.pop()
}
stk.push(i)
if(i >= k - 1) {
res.push(nums[stk[0]])
}
}
return res
};
Input
nums = [1], k = 1
Output
[1]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxSlidingWindow(self, nums, k):
cnt, heap, res = collections.Counter(), [], []
for i, num in enumerate(nums):
heapq.heappush(heap, -num)
cnt[num] += 1
while not cnt[-heap[0]]:
heapq.heappop(heap)
if i >= k - 1:
res.append(-heap[0])
cnt[nums[i - k + 1]] -= 1
return res
Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3,3,5,5,6,7]
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0239_SlidingWindowMaximum
{
public int[] MaxSlidingWindow(int[] nums, int k)
{
int n = nums.Length;
if (n * k == 0) return new int[0];
if (k == 1) return nums;
int[] left = new int[n];
int[] right = new int[n];
left[0] = nums[0];
right[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++)
{
if (i % k == 0) left[i] = nums[i];
else left[i] = Math.Max(left[i - 1], nums[i]);
var j = n - i - 1;
if ((j + 1) % k == 0) right[j] = nums[j];
else right[j] = Math.Max(right[j + 1], nums[j]);
}
var result = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++)
result[i] = Math.Max(left[i + k - 1], right[i]);
return result;
}
}
}
Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3,3,5,5,6,7]