▲

3

▼

🔽 Эффективная обработка диапазонных изменений и жадный подход к нахождению оптимального их количества

leetcoder, 13-03-2025 , 574

Ссылка на задачу — 3356. Zero Array Transformation II.

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

Дан массив nums длины N и список запросов queries, каждый из которых задаётся как [li, ri, vali]. Запрос означает, что значения в диапазоне [li, ri] можно уменьшить на любое число от 0 до vali независимо друг от друга.

Нужно найти минимальное число первых запросов k, после которых nums может превратится в массив, состоящий только из нулей. Если это невозможно — вернуть -1.

💡 Идея

Вместо того, чтобы изменять nums напрямую, будем хранить массив последовательных изменений к декременту (updates). Он позволяет эффективно применять диапазонные операции без лишних вычислений.

Чтобы минимизировать количество обработанных запросов, будем использовать жадную стратегию обработки запросов:

• Обрабатываем nums последовательно
• Для каждой позиции i, если nums[i] ещё не стал 0, пытаемся применить минимально возможное число новых запросов из списка.

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

1. Используем массив updates (N+1 элементов), где updates[i] хранит последовательные изменения к декременту значений.
2. Итерируемся по nums, применяя накопленные изменения к декременту.
3. Если nums[i] остаётся положительным, жадно берём запросы из списка.
4. Возвращаем количество использованных запросов или -1, если массив не удалось обнулить.

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

• Время: O(N + Q), где N — длина nums, Q — число запросов.
  • Каждый запрос обрабатывается только один раз → O(Q).
  • Каждое nums[i] проверяется ровно один раз → O(N).
• Память: O(N), так как массив updates имеет размер N+1.

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

impl Solution {
    pub fn min_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
        let mut updates = vec![0; nums.len() + 1]; // Tracks decrement changes over the range
        let mut queries = queries.into_iter(); // Efficiently consume queries
        let mut processed_queries = 0;

        let mut accumulated_decrement = 0;
        for (i, num) in nums.into_iter().enumerate() {
            // Process queries until we can make nums[i] zero
            while num > accumulated_decrement + updates[i] {
                if let Some(q) = queries.next() {
                    let (left, right, decrement) = (q[0] as usize, q[1] as usize, q[2]);

                    if i <= right {
                        updates[right + 1] -= decrement;
                        updates[left.max(i)] += decrement;
                    }
                    processed_queries += 1;
                } else {
                    return -1; // No more queries left to process
                }
            }
            accumulated_decrement += updates[i];
        }

        processed_queries
    }
}

Tags: #rust #algorithms #greedy