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

😎 Решение:

import java.util.PriorityQueue

class Solution {
    fun longestSubarray(nums: IntArray, limit: Int): Int {
        val maxHeap = PriorityQueue<IntArray> { a, b -> b[0] - a[0] }
        val minHeap = PriorityQueue<IntArray>(compareBy { it[0] })
        var left = 0
        var maxLength = 0

        for (right in nums.indices) {
            maxHeap.offer(intArrayOf(nums[right], right))
            minHeap.offer(intArrayOf(nums[right], right))

            while (maxHeap.peek()[0] - minHeap.peek()[0] > limit) {
                left = minOf(maxHeap.peek()[1], minHeap.peek()[1]) + 1
                while (maxHeap.peek()[1] < left) maxHeap.poll()
                while (minHeap.peek()[1] < left) minHeap.poll()
            }

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

        return maxLength
    }
}

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