Задача: 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 как результат.

😎 Решение:

class Solution {
    func longestSubarray(_ nums: [Int], _ limit: Int) -> Int {
        var maxHeap = [(Int, Int)]()
        var minHeap = [(Int, Int)]()
        var left = 0
        var maxLength = 0

        for right in 0..<nums.count {
            maxHeap.append((nums[right], right))
            minHeap.append((nums[right], right))

            while maxHeap.max()!.0 - minHeap.min()!.0 > limit {
                left = min(maxHeap.first(where: { $0.1 >= left })!.1, minHeap.first(where: { $0.1 >= left })!.1) + 1
                maxHeap = maxHeap.filter { $0.1 >= left }
                minHeap = minHeap.filter { $0.1 >= left }
            }

            maxLength = max(maxLength, right - left + 1)
        }

        return maxLength
    }
}

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