LeetCode 239 Sliding Window Maximum

LeetCode 239 Sliding Window Maximum

Link: leetcode.com/problems/sl…

Method: Double-endian queue

Time complexity: O(n)

Space complexity: O(n)

Idea: This is a difficult problem to start with, but I’ve already written about this method in LeetCode 1438, so it should be very easy to review backwards. It’s a two-ended queue that dynamically maintains Max values, putting elements from Last, and fetching Max values from First. For example, if we want to find the maximum value of a sliding window, we must use a two-ended queue to maintain the maximum value, so that the queue from First to Last direction must be monotonically decreasing or not increasing (depending on the problem). So for this problem, you can put indexes in the queue, you can put values in the queue.

We first consider in values, for example I have three 3 sliding window, move to the right, left border to delete a value, one thousand is 3, delete it, then, we need to ensure the queue with two 3, that is to say that we have to maintain a sequence does not increase monotonically, meets the left boundary value is equal to the queue value most daring delete directly.

Can I do index if I put it in? I can do that, too, because if I put index, when I move the left edge, I can just check if the left edge is the value of the First end of the queue, so if I use index, I can either decrement monotonically or not increment monotonically. The following code only puts a value, but changing to index is not difficult at all.

Code:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> maxQ = new ArrayDeque<>();
        
        int i = 0;
        for (; i < k - 1; i++) {
            while(! maxQ.isEmpty() && maxQ.peekLast() < nums[i]) { maxQ.pollLast(); } maxQ.addLast(nums[i]); }int[] res = new int[n - k + 1];
        for (; i < n; i++) {
            while(! maxQ.isEmpty() && maxQ.peekLast() < nums[i]) { maxQ.pollLast(); } maxQ.addLast(nums[i]); res[i - k +1] = maxQ.peekFirst();
            
            if (maxQ.peekFirst() == nums[i - k + 1]) { maxQ.pollFirst(); }}returnres; }}Copy the code