Очередная задача — 2375. Construct Smallest Number From DI String сходу выглядит переборной, но может быть эффективно реализована за счёт использования графовых алгоритмов.
📝 Описание задачи
Дан строковый шаблон pattern, состоящий из символов I и D.
Необходимо построить лексикографически наименьшее число длины n+1, используя цифры от 1 до 9 без повторений, которое соответствует следующим требованиям:
'I' (увеличение) на позиции i → требует, чтобы num[i] < num[i+1].'D' (уменьшение) на позиции i → требует, чтобы num[i] > num[i+1].
💡 Идея
Рассмотрим шаблон как ориентированный граф, где каждая позиция (i) — это вершина.
- Если
pattern[i] == 'I', создаём ребро i → i+1.
- Если
pattern[i] == 'D', создаём ребро i+1 → i.
После построения графа можно выполнить топологическую сортировку, начиная с вершин с нулевой степенью захода.
Чтобы гарантировать лексикографически наименьший порядок, обрабатываем вершины через приоритетную очередь (Min-Heap).
⚙️ Детали подхода
- Построение графа
- Создаём список смежности (
graph) и массив степеней захода (in_degree).
'I' → добавляем ребро i → i+1, увеличиваем in_degree[i+1].'D' → добавляем ребро i+1 → i, увеличиваем in_degree[i].
- Инициализация Мин-Кучи
- Добавляем все вершины с нулевой степенью захода в Min-Heap.
- Топологическая сортировка
- Достаём минимальную вершину из кучи, назначаем ей следующую минимальную цифру.
- Уменьшаем степени захода её соседей.
- Если у соседа становится нулевая степень захода, добавляем его в
Min-Heap.
- Формируем результат
- После обработки всех вершин собираем итоговую строку.
⏳ Асимптотика
-
Временная сложность:
O(n·log n)
- Построение графа:
O(n)
- Операции с кучей (
push и pop для n элементов): O(n·log n)
-
📦 Пространственная сложность:
O(n)
(граф, массив in_degree, мин-куча и результат).
📜 Исходный код
use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
pub fn smallest_number(pattern: String) -> String {
let n = pattern.len() + 1;
// Step 1: Build graph and compute in-degree
let mut graph = vec![Vec::new(); n];
let mut in_degree = vec![0; n];
for (i, ch) in pattern.chars().enumerate() {
if ch == 'I' {
graph[i].push(i + 1); // i → i+1
in_degree[i + 1] += 1;
} else {
graph[i + 1].push(i); // i+1 → i
in_degree[i] += 1;
}
}
// Step 2: Initialize min-heap with zero in-degree nodes
let mut min_heap = BinaryHeap::new();
for i in 0..n {
if in_degree[i] == 0 {
min_heap.push(Reverse(i)); // Reverse to create a min-heap
}
}
// Step 3: Process nodes in topological order
let mut result = vec![' '; n];
let mut next_digit = '1';
while let Some(Reverse(node)) = min_heap.pop() {
result[node] = next_digit;
next_digit = ((next_digit as u8) + 1) as char;
for &neighbor in &graph[node] {
in_degree[neighbor] -= 1;
if in_degree[neighbor] == 0 {
min_heap.push(Reverse(neighbor));
}
}
}
result.into_iter().collect()
}
}
Tags: #rust #algorithms #graph