Задача: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Сложность: medium

Дан массив целых чисел nums и целое число limit. Вернуть размер самой длинной непустой подстроки, такая что абсолютная разница между любыми двумя элементами этой подстроки меньше или равна limit.

Пример:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

👨‍💻 Алгоритм:

1⃣Инициализировать два дека (minDeque и maxDeque) для хранения минимальных и максимальных значений в текущем окне и переменную left для начала окна.

2⃣Итеративно добавлять элементы в дек, поддерживая условие абсолютной разницы между максимальным и минимальным элементом в окне, чтобы она была не больше limit, при необходимости сдвигая left.

3⃣Обновлять maxLength, проверяя максимальную длину текущего окна, и возвращать maxLength как результат.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestSubarray(int[] nums, int limit) {
        var maxHeap = new SortedSet<(int Value, int Index)>(Comparer<(int, int)>.Create((a, b) => a.Value == b.Value ? a.Index.CompareTo(b.Index) : b.Value.CompareTo(a.Value)));
        var minHeap = new SortedSet<(int Value, int Index)>(Comparer<(int, int)>.Create((a, b) => a.Value == b.Value ? a.Index.CompareTo(b.Index) : a.Value.CompareTo(b.Value)));
        int left = 0, maxLength = 0;

        for (int right = 0; right < nums.Length; ++right) {
            maxHeap.Add((nums[right], right));
            minHeap.Add((nums[right], right));

            while (maxHeap.Min.Value - minHeap.Max.Value > limit) {
                left = Math.Min(maxHeap.Min.Index, minHeap.Max.Index) + 1;
                while (maxHeap.Min.Index < left) {
                    maxHeap.Remove(maxHeap.Min);
                }
                while (minHeap.Max.Index < left) {
                    minHeap.Remove(minHeap.Max);
                }
            }

            maxLength = Math.Max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

Ставь 👍 и забирай 📚 Базу знаний