239. Sliding Window Maximum

LeetCode hard original: C# #array #csharp #hard #leetcode #queue #sliding-window
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
LeetCode Static

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

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

Ejemplo

Input: nums = [1], k = 1

Output: [1]

C# solución

coincidente/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++ solución

borrador automático, revisar antes de enviar 
#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 solución

coincidente/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 solución

coincidente/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 solución

coincidente/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 solución

coincidente/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
}

Algorithm

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

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

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

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

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

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

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

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

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

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

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

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

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

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

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes
Todavía no hay vacantes activas.