Для задачи 769. Max Chunks To Make Sorted у меня есть очень короткое решение, а значит и разбор не стоит делать длинным ;)
Задача: Максимальное количество отсортированных блоков 🧩
Дана перестановка arr длины n. Нужно разделить массив на максимальное количество блоков, таких, что, отсортировав каждый блок по отдельности и объединив их, получится полностью отсортированный массив.
Идея
Вводим функцию баланса, зависящую от частичных сумм по индексам и значениям. Каждый новый блок формируем при нулевых балансах.
Подход
Напишем код самым коротким и непонятным читателю образом, как только умеем.
Сложность:
O(n) по времениO(1) по памяти
Исходный код
impl Solution {
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
arr.into_iter().enumerate().fold(
(0, 0), |acc, (val, idx)| (
acc.0 + val as i64 - idx as i64,
acc.1 - (acc.0.abs()-1).min(0) as i32)
).1
}
}
Честный разбор с решением, которое не стыдно показать на собеседовании, я всё же сделаю :)
Идея 💡
Задача состоит в том, чтобы разделить массив на максимальное количество блоков, так чтобы сортировка каждого блока и их объединение давали отсортированный массив. Ключевая идея заключается в том, что элементы из одного цикла перестановки
arr1 → arr2 → arr3 → ... → arrn → arr1
обязательно должны находиться в одном блоке, так как они взаимозависимы.
Описание подхода 🛠️
- Создаём массив
chunk_assignment, чтобы отслеживать принадлежность каждого индекса к определённому блоку.
- Используем функцию
assign_chunk для рекурсивного назначения всех индексов, связанных с текущим индексом, в один блок. Она:
- Обновляет максимальный индекс текущего блока.
- Помечает все посещённые индексы текущим номером блока.
- Внешний цикл:
- Перебирает индексы массива.
- Увеличивает счётчик блоков при обнаружении нового блока.
- Завершает обработку текущего блока, когда все его элементы покрыты.
- Возвращаем общее количество блоков
Асимптотика 📊
- Время:
O(n), так как каждый элемент обрабатывается один раз.
- Память:
O(n), для хранения массива chunk_assignment.
Исходный код решения 📜
impl Solution {
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
let n = arr.len();
let mut chunk_assignment = vec![0; n]; // Tracks which chunk each index belongs to
let mut chunk_count = 0; // Counter for the number of chunks
// Helper function to assign indices to a chunk
let mut assign_chunk = |start_idx: usize, chunk: i32, max_idx: &mut usize| {
let mut current_idx = start_idx;
while chunk_assignment[current_idx] == 0 {
*max_idx = (*max_idx).max(current_idx);
chunk_assignment[current_idx] = chunk;
current_idx = arr[current_idx] as usize;
}
};
let mut start_idx = 0;
while start_idx < n {
chunk_count += 1; // Start a new chunk
let mut max_idx = start_idx;
// Process the current chunk until all related indices are covered
loop {
assign_chunk(start_idx, chunk_count, &mut max_idx);
if start_idx == max_idx {
break; // The current chunk is complete
}
start_idx += 1; // Move to the next index
}
start_idx += 1; // Move to the next unprocessed index
}
chunk_count // Return the total number of chunks
}
}