Question

Formatted question description: https://leetcode.ca/all/239.html

Level

Hard

Description

Given an array 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:

Input: nums = [1,3,-1,-3,5,3,6,7], and 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

Note:

You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:

Could you solve it in linear time?

Algorithm

Use double-ended queue, where insertion and deletion can take place at both ends of the queue in O(1) time complexity. To make sure a sliding window of size k is maintained, store indices, not actual numbers, in the double-ended queue deque.

For the first k elements from nums, directly add them into deque without considering the window size, since the number of elements does not exceed k. Before adding each element, first check whether the number represented by the last element in deque (this means that if the last element in deque is i, then the number represented by the last eoement in deque is nums[i]) is less than the current number. If so, remove the last element from deque until deque becomes empty or the number represented by the last element in deque is greater than or equal to the current number. The first element in deque is the index of the maximum element in the first window of size k. Obtain the maximum element and put it in the first position of the result array (the first position means index 0).

Then loop over nums from index k to the end. For each index i, first check whether the first element in deque equals i - k. If so, then the first element is not in the current window, so remove the first element. Then if the number represented by the last element in deque is less than the current number, remove the last element from deque until deque becomes empty or the number represented by the last element in deque is greater than or equal to the current number. The first element in deque is the index of the maximum element in the current sliding window of size k. Obtain the maximum element and put it in the current position of the result array.

Finally, return the result array.

Example illustration:

input: 1,3,-1,-3,5,3,6,7

(q: right end in, left front out)

iteration-1: q[0]
iteration-2: q[0,1]
iteration-3: q[0,1,2]

iteration-4: poll: q[1,2]
                poll-last: none
                offer q[1,2,3]
                max: nums[1]

iteration-5: poll: q[2,3]
                poll-last: q[2]
                poll-last: q[]
                offer: q[4]
                max: nums[4]

iteration-6: poll: none
                poll-last: none
                offer: q[4,5]
                max: nums[4]

iteration-7: poll: none
                poll-last: q[5]
                poll-last: q[]
                offer: q[6]
                max: nums[6]

iteration-8: poll: none
                poll-last: q[]
                offer: q[7]
                max: nums[7]

Code

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Sliding_Window_Maximum {

    public static void main(String[] args) {
        Sliding_Window_Maximum out = new Sliding_Window_Maximum();
        Solution s = out.new Solution();

        System.out.println(Arrays.toString(s.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
    }

    /*
        Deque<String> dq = new ArrayDeque<>();
        dq.offer("a");
        dq.offer("b");
        dq.offer("c");
        System.out.println(dq.peek()); // a
        System.out.println(dq.peekFirst()); // a
        System.out.println(dq.peekLast()); // c
     */

    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return new int[0];
            }

            int n = nums.length;
            int[] result = new int[n - k + 1];
            int resultPointer = 0;

            // store index of nums array
            // q is descending values (its indexes)
            // eg. [6,5,4,3,2,1], q will be: [6,5,4], then [5,4,3], then [4,3,2], then [3,2,1]
            Deque<Integer> q =  new ArrayDeque<>();

            for (int i = 0; i < nums.length; i++) {
                // remove index not in k-window
                while (!q.isEmpty() && q.peek() < i - k + 1) { // peek() head of queue
                    q.poll();
                }

                // remove use-less index in q
                while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) { // peekLast() last of queue
                    q.pollLast();
                }

                q.offer(i);

                // start from k-th element, there is a max for window
                if (i >= k - 1) {
                    result[resultPointer] = nums[q.peek()];
                    resultPointer++;
                }
            }

            return result;
        }
    }
}

############

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0, j = 0; i < n; ++i) {
            if (!q.isEmpty() && i - k + 1 > q.peekFirst()) {
                q.pollFirst();
            }
            while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
                q.pollLast();
            }
            q.offer(i);
            if (i >= k - 1) {
                ans[j++] = nums[q.peekFirst()];
            }
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/sliding-window-maximum/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& A, int k) {
        vector<int> ans;
        deque<int> q;
        for (int i = 0; i < A.size(); ++i) {
            if (q.size() && q.front() == i - k) q.pop_front();
            while (q.size() && A[q.back()] <= A[i]) q.pop_back();
            q.push_back(i);
            if (i >= k - 1) ans.push_back(A[q.front()]);
        }
        return ans;
    }
};

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        ans = []
        for i, v in enumerate(nums):
            if q and i - k + 1 > q[0]:
                q.popleft() # remove index if out of window left
            while q and nums[q[-1]] <= v:
                q.pop()
            q.append(i)
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans

############

class Solution(object):
  def maxSlidingWindow(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: List[int]
    """
    if k == 0:
      return []
    ans = [0 for _ in range(len(nums) - k + 1)]
    stack = collections.deque([])
    for i in range(0, k):
      while stack and nums[stack[-1]] < nums[i]:
        stack.pop()
      stack.append(i)
    ans[0] = nums[stack[0]]
    idx = 0
    for i in range(k, len(nums)):
      idx += 1
      if stack and stack[0] == i - k:
        stack.popleft()
      while stack and nums[stack[-1]] < nums[i]:
        stack.pop()
      stack.append(i)
      ans[idx] = nums[stack[0]]

    return ans

func maxSlidingWindow(nums []int, k int) (ans []int) {
	q := []int{}
	for i, v := range nums {
		if len(q) > 0 && i-k+1 > q[0] {
			q = q[1:]
		}
		for len(q) > 0 && nums[q[len(q)-1]] <= v {
			q = q[:len(q)-1]
		}
		q = append(q, i)
		if i >= k-1 {
			ans = append(ans, nums[q[0]])
		}
	}
	return ans
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    let ans = [];
    let q = [];
    for (let i = 0; i < nums.length; ++i) {
        if (q && i - k + 1 > q[0]) {
            q.shift();
        }
        while (q && nums[q[q.length - 1]] <= nums[i]) {
            q.pop();
        }
        q.push(i);
        if (i >= k - 1) {
            ans.push(nums[q[0]]);
        }
    }
    return ans;
};

using System.Collections.Generic;

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        if (nums.Length == 0) return new int[0];
        var result = new int[nums.Length - k + 1];
        var descOrderNums = new LinkedList<int>();
        for (var i = 0; i < nums.Length; ++i)
        {
            if (i >= k && nums[i - k] == descOrderNums.First.Value)
            {
                descOrderNums.RemoveFirst();
            }
            while (descOrderNums.Count > 0 && nums[i] > descOrderNums.Last.Value)
            {
                descOrderNums.RemoveLast();
            }
            descOrderNums.AddLast(nums[i]);
            if (i >= k - 1)
            {
                result[i - k + 1] = descOrderNums.First.Value;
            }
        }
        return result;
    }
}

239 - Sliding Window Maximum

Question

Level

Description

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Level

Description

Algorithm

Code

All Problems

All Solutions