Самый большой подмассив, у которого абсолютная разница между любой парой его элементов не выше порога
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Дан массив целых чисел nums и целочисленный порог limit, вернуть размер самого длинного не пустого подмассива, у которого абсолютная разность между его двумя любыми элементами не превышает limit.
Пример 1:
Дано: nums = [8,2,4,7], limit = 4 Результат: 2 Пояснение: Все подмассивы: [8] максимальная абсолютная разность |8-8| = 0 <= 4. [8,2] максимальная абсолютная разность |8-2| = 6 > 4. [8,2,4] максимальная абсолютная разность |8-2| = 6 > 4. [8,2,4,7] максимальная абсолютная разность |8-2| = 6 > 4. [2] максимальная абсолютная разность |2-2| = 0 <= 4. [2,4] максимальная абсолютная разность |2-4| = 2 <= 4. [2,4,7] максимальная абсолютная разность |2-7| = 5 > 4. [4] максимальная абсолютная разность |4-4| = 0 <= 4. [4,7] максимальная абсолютная разность |4-7| = 3 <= 4. [7] максимальная абсолютная разность |7-7| = 0 <= 4. Подмассивы, которые соответствуют условию задачи, имеют размер в 1-2 элемента, поэтому размер наибольшего подмассива = 2.
Пример 2:
Дано: nums = [10,1,2,4,7,2], limit = 5 Результат: 4 Пояснение: Подмассив [2,4,7,2] самый длинный с максимальной абсолютной разностью |2-7| = 5 <= 5.
Пример 3:
Дано: nums = [4,2,2,2,4,4,2,2], limit = 0 Результат: 3
Ограничения:
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= limit <= 109
Идея решения
"Абсолютная разность между двумя любыми элементами не превышает порог" => Абсолютная разница между минимальным и максимальным элементами подмассива.
А значит, нам нужно найти самый длинный подмассив, у которого абсолютная разница минимального и максимального элемента не превышает заданный порог. Для этого нам нужно два указателя: левый (left) и правый (right). И для каждого правого указателя мы находим его левый указатель, который будем смещать вправо. И замерять расстояние между указателями. Надо найти такое расположение указателей, чтобы расстояние было максимальным.
Для этого мы будем использовать структуру Dequeue (двухсторонняя очередь). С одной стороны, у нас будет список кандидатов в максимальные элементы, расположенных в убывающем порядке. И каждый раз, как правый указатель перейдет на новую позицию, нам нужно сделать dequeue хвостовых элементов, которые меньше, чем num[right]. Так как эти элементы "старого маленького хвоста" никогда больше не будут максимальным диапазоном. После «очистки» элементов «старого маленького хвоста» добавьте nums[right] в двухстороннюю очередь, и тогда голова двухсторонней очереди является текущим максимумом.
То же самое для Deque с минимальными элементами. Сдвигаем правый указатель на 1 и очищаем элементы "старого большого хвоста", добавляем nums[right], начало двухсторонней очереди является текущим минимумом.
Что мы должны сделать дальше, так это уменьшить левый указатель из-за порога. Если current.max - current.min > limit. Мы должны переместить левый указатель. Соответственно, нам нужно обновить наши min/max Dequeue. Если голова max Deque равен nums[left], значит, это тот, который нам нужно удалить из очереди, так как мы собираемся переместить левый указатель на 1. (Примечание: nums[left] никогда не будет больше чем заголовок max Deque, и если nums[left] меньше, чем голова, все в порядке, продолжайте перемещать указатель влево, пока не будет достигнуто ограничение).
Имплементация
class Solution {
public int longestSubarray(int[] nums, int limit) {
Deque<Integer> maxDeque = new LinkedList<>();
Deque<Integer> minDeque = new LinkedList<>();
int res = 1;
int l = 0;
// увеличиваем правый указатель и смотрим, что мы можем сделать с левым
for (int r = 0; r < nums.length; ++r) {
// обновляем maxDeque значением, на которое указвает правый указатель
while (!maxDeque.isEmpty() && maxDeque.peekLast() < nums[r]) {
maxDeque.removeLast();
}
maxDeque.addLast(nums[r]); // добавляем правый элемент
// обновляем minDeque
значением, на которое указвает правый указатель
while (!minDeque.isEmpty() && minDeque.peekLast() > nums[r]) {
minDeque.removeLast();
}
minDeque.addLast(nums[r]); // добавляем правый элемент
// смещаем левый указатель, если улсовие задачи не соблюдено
while (maxDeque.peekFirst() - minDeque.peekFirst() > limit) {
if (maxDeque.peekFirst() == nums[l]) {
// System.out.println("Max: l=" + l + "; nums[l] = " + nums[l] + "; r=" + r);
maxDeque.pollFirst();
}
if (minDeque.peekFirst() == nums[l]) {
// System.out.println("Min: l=" + l + "; nums[l] = " + nums[l] + "; r=" + r);
minDeque.pollFirst();
}
++l; // shrink it!
}
// обновляем результат
res = Math.max(res, r - l + 1);
}
return res;
}
}
Комментарии
Отправить комментарий