▲

3

▼

🔥 Поиск наибольшего «красивого» подмассива методом скользящего окна в чистом функциональном стиле

leetcoder, 18-03-2025 , 177

Ссылка на задачу — 2401. Longest Nice Subarray.

📌 Описание задачи

Дан массив nums, состоящий из целых чисел.
Нужно найти наибольший подмассив, в котором ни одна пара чисел не имеет общих установленных битов
(т.е. их побитовое И (&) равно 0).

• 📥 Вход: nums = [1, 3, 8, 48, 10]
• 📤 Выход: 3
• 🔍 Пояснение: Наибольший "красивый" подмассив: [3, 8, 48], так как:
  • 3 & 8 = 0
  • 3 & 48 = 0
  • 8 & 48 = 0
  • Никакой больший подмассив не удовлетворяет условиям.

💡 Идея

Будем решать задачу в чистом функциональном стиле, используя технику скользящего окна.

• Расширяем окно вправо, если nums[right] не конфликтует с текущим битовым множеством.
• Сжимаем окно слева, если появляется конфликт.
• Отслеживаем текущее битовое множество (cur_bitset), обновляя его при изменении окна.

⚙️ Детали подхода

1. Используем рекурсию вместо циклов, передавая:
   • left и right – соответствующие слайсы для левой и правой границ окна.
   • cur_bitset – текущее битовое множество.
   • cur_len – длину текущего окна.
   • max_len – максимальную длину найденного подмассива.
2. База рекурсии – если right достиг конца (оказался пустым), возвращаем max_len.
3. Расширяем окно, если right[0] не имеет битовых конфликтов.
4. Сжимаем окно, если конфликт возникает, удаляя left[0] из битового множества.

📊 Асимптотика

• Время: O(N) – каждый элемент добавляется и удаляется не более одного раза.
• Память: O(1) в случае TCO (Tail Call Optimization);
  • так как компилятор Rust не даёт нам гарантий для TCO, то в худшем случае потребление памяти будет O(N) на стэк вызовов.

💻 Исходный код

impl Solution {
    pub fn longest_nice_subarray(nums: Vec<i32>) -> i32 {
        // Recursive helper function to maintain the sliding window
        fn slide_window_iter(left: &[i32], right: &[i32], cur_bitset: i32, cur_len: i32, max_len: i32) -> i32 {
            match right.first() {
                // Base case: when the right pointer reaches the end 
                None => max_len, 
                // Expand window if `right_val` has no bitwise conflicts
                Some(right_val) if cur_bitset & right_val == 0 
                  => slide_window_iter(left, &right[1..], cur_bitset | right_val, cur_len + 1, max_len.max(cur_len + 1)),
                // Shrink window from the left when there is a conflict
                _ => slide_window_iter(&left[1..], right, cur_bitset ^ left[0], cur_len - 1, max_len)
            }
        }

        // Start recursion with the full input array
        slide_window_iter(&nums, &nums, 0, 0, 0)
    }
}

Tags: #rust #algorithms #slidewindow