239. Sliding Window Maximum

leetcode hard

#array#csharp#hard#leetcode#queue#sliding-window

Task

Вам дан массив целых чисел nums. Существует скользящее окно размера k, которое перемещается с самого левого конца массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.

Верните максимальные значения скользящего окна.

Пример

Input: nums = [1], k = 1

Output: [1]

C# solution

matched/original

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        LinkedList<int> dq = new LinkedList<int>();
        List<int> res = new List<int>();
        for (int i = 0; i < k; i++) {
            while (dq.Count != 0 && nums[i] >= nums[dq.Last.Value]) {
                dq.RemoveLast();
            }
            dq.AddLast(i);
        }
        res.Add(nums[dq.First.Value]);
        for (int i = k; i < nums.Length; i++) {
            if (dq.First.Value == i - k) {
                dq.RemoveFirst();
            }
            while (dq.Count != 0 && nums[i] >= nums[dq.Last.Value]) {
                dq.RemoveLast();
            }
            dq.AddLast(i);
            res.Add(nums[dq.First.Value]);
        }
        return res.ToArray();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& MaxSlidingWindow(vector<int>& nums, int k) {
        LinkedList<int> dq = new LinkedList<int>();
        List<int> res = new List<int>();
        for (int i = 0; i < k; i++) {
            while (dq.size() != 0 && nums[i] >= nums[dq.Last.Value]) {
                dq.RemoveLast();
            }
            dq.AddLast(i);
        }
        res.push_back(nums[dq.First.Value]);
        for (int i = k; i < nums.size(); i++) {
            if (dq.First.Value == i - k) {
                dq.RemoveFirst();
            }
            while (dq.size() != 0 && nums[i] >= nums[dq.Last.Value]) {
                dq.RemoveLast();
            }
            dq.AddLast(i);
            res.push_back(nums[dq.First.Value]);
        }
        return res.ToArray();
    }
}

Java solution

matched/original

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new LinkedList<>();
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
                dq.pollLast();
            }
            dq.offerLast(i);
        }
        res.add(nums[dq.peekFirst()]);

        for (int i = k; i < nums.length; i++) {
            if (dq.peekFirst() == i - k) {
                dq.pollFirst();
            }
            while (!dq.isEmpty() && nums[i] >= nums

JavaScript solution

matched/original

class Solution {
    maxSlidingWindow(nums, k) {
        const dq = []
        const res = []

        for (let i = 0; i < k; i++) {
            while (dq.length && nums[i] >= nums[dq[dq.length - 1]]) {
                dq.pop()
            }
            dq.push(i)
        }
        res.push(nums[dq[0]])

        for (let i = k; i < nums.length; i++) {
            if (dq[0] == i - k) {
                dq.shift()
            }
            while (dq.length && nums[i] >= nums[dq[dq.length - 1]]) {
                dq.pop()
            }
            dq.push(i)
            res.push(nums[dq[0]])
        }

        return res
    }
}

Python solution

matched/original

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = collections.deque()
        res = []

        for i in range(k):
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)
        res.append(nums[dq[0]])

        for i in range(k, len(nums)):
            if dq[0] == i - k:
                dq.popleft()
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)
            res.append(nums[dq[0]])

        return res

Go solution

matched/original

func maxSlidingWindow(nums []int, k int) []int {
    dq := make([]int, 0)
    res := make([]int, 0)
    
    for i := 0; i < k; i++ {
        for len(dq) > 0 && nums[i] >= nums[dq[len(dq)-1]] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
    }
    res = append(res, nums[dq[0]])
    
    for i := k; i < len(nums); i++ {
        if dq[0] == i - k {
            dq = dq[1:]
        }
        for len(dq) > 0 && nums[i] >= nums[dq[len(dq)-1]] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
        res = append(res, nums[dq[0]])
    }
    
    return res
}

Explanation

Algorithm

Инициализация и заполнение первой части окна:

Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов.

Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента:

Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].

Добавьте текущий индекс i в конец dq.

Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]].

Сканирование оставшейся части массива:

Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента:

Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна.

Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].

Добавьте текущий индекс i в конец dq.

Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]].

Возвращение результата:

Верните список res, содержащий максимальные элементы для каждого скользящего окна.

😎