▲

3

▼

🚀 Однопроходный жадный скан для задачи максимизации функционала на триплетах

leetcoder, 02-04-2025

Условие задачи — 2874. Maximum Value of an Ordered Triplet II.

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

Дан массив целых чисел nums (индексация с нуля).
Нужно найти максимум выражения (nums[i]-nums[j])·nums[k] среди всех троек индексов i < j < k.
Если все такие значения отрицательны, вернуть 0.

💡 Идея

Выражение (nums[i]-nums[j])·nums[k] будет наибольшим, при фиксированном k, если:

• Число nums[i] наибольшее
• Разность nums[i]-nums[j] максимальна

Значит, на каждом шаге мы можем поддерживать максимальное значение разности (nums[i]-nums[j]) до текущего индекса и умножать его на nums[k], обновляя лучший результат.

🔍 Детали подхода

1. Идем по массиву слева направо. На каждом шаге:
   • max_val хранит максимум из всех предыдущих чисел (nums[..i]);
   • max_diff — максимум nums[i]-nums[j] на текущий момент;
   • умножаем max_diff на текущий nums[k] и обновляем best.
2. Всё делается за один проход, без дополнительных структур данных.

⏱️ Асимптотика

• Время: O(n) — один проход по массиву
• Память: O(1) — используются только 3 переменные

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

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        nums.into_iter().fold((0i64, 0, 0), |(best, max_diff, max_val), x| (
            best.max(x as i64 * max_diff as i64),
            max_diff.max(max_val - x),
            max_val.max(x),
        )).0
    }
}

Tags: #rust #algorithms #greedy

▲

3

▼

📦 Однопроходный жадный алгоритм для разбивки строки на части, неразрывающие буквы

leetcoder, 30-03-2025

Ссылка на задачу — 763. Partition Labels.

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

• Дана строка s, состоящая только из строчных латинских букв.
• Нужно разбить строку на как можно большее количество подстрок, таких что каждая буква встречается не более чем в одной подстроке.
• После разбиения объединение всех подстрок в порядке следования должно дать исходную строку.
• Например, для строки "ababcc" корректное разбиение: ["abab", "cc"].
  А такие варианты, как ["aba", "bcc"] или ["ab", "ab", "cc"] — недопустимы, потому что буквы повторяются в нескольких частях.
• Нужно вернуть список размеров всех полученных подстрок.

💡 Идея

Каждая буква должна присутствовать в одной части.
Значит, можно рассматривать все буквы как интервалы [первая позиция, последняя позиция].
Теперь задача сводится к жадному объединению перекрывающихся интервалов: как только текущий интервал завершился, мы фиксируем подстроку.

🔍 Детали подхода

1. Проходим по строке один раз, чтобы:
   • определить первую и последнюю позицию каждой буквы;
   • зафиксировать порядок появления символов.
2. Затем проходим по символам алфавита в порядке первого появления:

Читать дальше →

▲

3

▼

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

leetcoder, 13-03-2025

Ссылка на задачу — 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] хранит последовательные изменения к декременту значений.

Читать дальше →