Сегодня рассмотрим достаточно простое решение задачи 2779. Maximum Beauty of an Array After Applying Operation.
Условие 📋
Дан массив nums и целое неотрицательное число k. Разрешается заменить каждый элемент массива (не более одного раза) любым числом из диапазона [nums[i]−k,nums[i]+k]. Требуется найти максимальную длину подпоследовательности массива, состоящей из одинаковых элементов (это называется "красота массива").
Идея 💡
Фактически задача сводится к нахождению наибольшего подмножества массива, все элементы которого укладываются в интервал длины 2×k. Чтобы эффективно найти такой диапазон, можно использовать метод скользящего окна по предварительно отсортированному массиву.
Подход 🛠️
- Сортировка массива: Упорядочиваем массив, чтобы элементы, которые могут принадлежать одному диапазону, оказались рядом.
- Скользящее окно: Используем два указателя (
l и r) для определения максимального диапазона, удовлетворяющего условию nums[r]−nums[l]≤2×k.
- Подсчёт длины диапазона: На каждом шаге обновляем результат как максимум текущей длины окна
r−l.
Асимптотика 📊
- Временная сложность:
O(nlogn) из-за сортировки + O(n) для скользящего окна, итого O(nlogn).
- Пространственная сложность:
O(1), если используется сортировка "на месте".
Исходный код решения
impl Solution {
pub fn maximum_beauty(nums: Vec<i32>, k: i32) -> i32 {
// Create a mutable copy of nums and sort it
let mut sorted_nums = nums.clone();
sorted_nums.sort_unstable();
let mut max_beauty = 0;
let mut right = 0;
// Iterate over each number in the sorted array
for left in 0..sorted_nums.len() {
// Expand the right pointer as long as the difference is within the allowed range
while right < sorted_nums.len() && sorted_nums[right] <= sorted_nums[left] + 2 * k {
right += 1;
}
// Update the maximum beauty based on the current window size
max_beauty = max_beauty.max((right - left) as i32);
}
max_beauty
}
}