В следующей задаче - 2661. First Completely Painted Row or Column можно не симулировать в лоб, и за счёт этого сэкономить память при решении (хоть и не получится асимптотически лучше).
📋 Описание задачи
- Нам дан массив
arr и матрица mat, содержащие числа от 1 до m * n.
- Массив
arr задаёт порядок закраски ячеек матрицы mat (закрашивается ячейка, содержащая указанное число).
- В следующем примере:
arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Необходимо найти первый такой индекс i в массиве arr, при котором:
- Либо вся строка, либо весь столбец матрицы окажется закрашенным.
💡 Идея
Задачу можно переформулировать:
- Каждая строка и каждый столбец закрашиваются, если все элементы строки/столбца обработаны в порядке массива
arr.
- Получается, что для решения задачи нужно:
- Найти максимальный индекс появления значений из
arr для каждой строки/столбца.
Читать дальше →
ответить
Следующая задача 407. Trapping Rain Water II даёт возможность потренировать пространственное воображение (по крайней мере на этапе выбора адекватного для её решения алгоритма).
📋 Описание задачи
Дана 3D-сетка, представляющая высоты ячеек. Необходимо вычислить объем воды, который можно удержать после дождя. Вода может заполнять только области, окруженные ячейками с большей высотой.
💡 Идея
Мы рассматриваем каждую ячейку как часть сетки, где вода может стекать только в соседние ячейки с меньшей или равной высотой. Используя структуру данных непересекающихся множеств (Disjoint-Set или Union-Find), мы группируем соединённые ячейки и отслеживаем их связь с границами, чтобы определить, какие ячейки могут удерживать воду.
🛠️ Детали подхода
-
Представление и сортировка:
- Преобразуем все ячейки в список, где каждая ячейка представлена своей высотой и координатами.
- Сортируем ячейки по высоте в порядке возрастания.
-
Структура объединения множеств:
- Создаем дискретное множество для ячеек, добавляя виртуальный узел для границ сетки.
Читать дальше →
ответить
Задача на сегодня 1368. Minimum Cost to Make at Least One Valid Path in a Grid - достаточно стандартная вариация лабиринта с бесплатными переходами.
📝 Описание задачи
У нас есть поле размером m×n, где каждая клетка содержит указание направления движения. Необходимо найти минимальную стоимость перехода из левого верхнего угла (0, 0) в правый нижний угол (m−1,n−1).
Каждая клетка указывает направление движения:
1 — вправо,2 — влево,3 — вниз,4 — вверх.
Изменение направления перехода возможно, но со стоимостью 1, и его можно выполнить только один раз для каждой клетки.
💡 Идея
Поле можно рассматривать как ориентированный граф, где клетки являются вершинами, а направления задают ребра. Наша цель — найти минимальную стоимость пути из начальной клетки в конечную. Для этого используется модифицированный BFS с двумя очередями, где приоритет отдается движениям без изменения направления.
🛠️ Детали подхода
- Две очереди:
Читать дальше →
ответить
Наша новая задача – 2425. Bitwise XOR of All Pairings решается "размышлениями на салфетке" и потом очень быстро и просто программируется.
📋 Описание задачи
Даны два массива nums1 и nums2, содержащие неотрицательные числа. Для каждой пары чисел, взятых из этих массивов, вычисляется побитовый XOR. Нужно вернуть результат XOR всех таких пар.
🧠 Идея
XOR обладает полезными свойствами:
- Результат XOR числа с самим собой равен
0 (a ^ a = 0).
- XOR ассоциативен и коммутативен, что позволяет упрощать вычисления.
Только если длина одного массива нечётная, элементы второго массива оказывают влияние на результат, так как они "непарные".
В итоге вклад в результат зависит от длины второго массива для каждого массива из входной пары.
😃 Детали подхода
- Найти длины массивов
nums1 и nums2.
- Если длина
nums2 нечётная, XOR всех элементов nums1 добавляется в результат.
- Если длина
nums1 нечётная, XOR всех элементов nums2 добавляется в результат.
- Возвратить результат как итоговый XOR.
⏱️ Асимптотика
-
Время:
O(n + m), где n и m — длины массивов nums1 и nums2.- XOR всех элементов каждого массива занимает линейное время.
-
Память:
O(1), используется небольшое число дополнительных переменных.
💻 Исходный код
use std::ops::BitXor;
impl Solution {
pub fn xor_all_nums(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let len_nums1 = nums1.len();
let len_nums2 = nums2.len();
// Initialize result as 0
let mut result = 0;
// If nums1 has an odd number of elements, XOR all elements of nums2
if len_nums1 % 2 == 1 {
result ^= nums2.into_iter().fold(0, i32::bitxor);
}
// If nums2 has an odd number of elements, XOR all elements of nums1
if len_nums2 % 2 == 1 {
result ^= nums1.into_iter().fold(0, i32::bitxor);
}
result
}
}
Сегодня у нас интересная задача на битовые манипуляции – 2429. Minimize XOR.
📜 Описание задачи
Дано два положительных числа num1 и num2. Нужно найти число x, такое что:
- Количество установленных битов в числе
x равно количеству установленных битов в num2.
- Результат операции
XOR между x и num1 минимален.
💡 Идея
Для минимизации XOR мы
- Стремимся сохранить как можно больше старших битов из числа num1, так как они оказывают наибольшее влияние на минимизацию результата.
- Если остаются неиспользованные биты, мы добавляем младшие биты, чтобы завершить формирование числа x с требуемым количеством установленных битов.
✨ Детали подхода
-
Подсчёт установленных битов:
- Используем метод
count_ones, чтобы подсчитать количество установленных битов в числе num2.
-
Сохранение старших битов:
- Проходим по битам
num1 с самого старшего до младшего.
- Если бит установлен, включаем его в результат и уменьшаем счётчик оставшихся битов.
Читать дальше →
1 ответ
Задача на сегодня 2657. Find the Prefix Common Array of Two Arrays решается в лоб, но иногда стоит рассматривать и такие простые!
📝 Описание задачи
Даны две перестановки целых чисел A и B длины n. Необходимо вычислить массив общего префикса C, где C[i] равен количеству чисел, присутствующих в обеих перестановках на индексах от 0 до i.
Пример:
- Input:
A = [1,3,2,4], B = [3,1,2,4]
- Output:
[0,2,3,4]
💡 Идея
Чтобы быстро подсчитать количество общих элементов в префиксе, мы будем использовать два булевых массива для отслеживания того, какие элементы уже встречались в каждой из перестановок. Это позволит эффективно определять, какие элементы являются общими на каждом шаге.
📋 Подробности подхода
- Создаем два булевых массива
seen_in_a и seen_in_b длины n + 1 для отслеживания элементов, уже встреченных в A и B.
- Проходим по массивам
A и B одновременно:
- Помечаем текущие элементы
A[i] и B[i] как "увиденные".
- Увеличиваем счетчик общих элементов, если текущий элемент уже был встречен в другом массиве.
- На каждом шаге добавляем текущее значение счетчика общих элементов в результат.
Читать дальше →
ответить
Сегодня мы рассмотрим решение задачи 2116. Check if a Parentheses String Can Be Valid.
🧩 Описание задачи
Дана строка s, состоящая только из символов '(' и ')', и строка locked длины n, состоящая из символов '0' и '1'. Каждая позиция в locked указывает, можно ли изменить символ в s на этой позиции:
- Если
locked[i] == '1', символ s[i] нельзя менять.
- Если
locked[i] == '0', символ s[i] можно изменить на '(' или ')'.
Нужно определить, можно ли сделать строку s корректной скобочной записью.
💡 Идея
Решение основывается на двух проходах по строке:
- Прямой проход: Проверяем баланс открывающих и закрывающих скобок слева направо, учитывая символы, которые можно менять.
- Обратный проход: Инвертируем строку (меняем '(' на ')' и наоборот) и проверяем баланс справа налево.
При каждом проходе используем два счётчика:
- balance для отслеживания текущего баланса скобок.
- free для отслеживания количества символов, которые можно изменить.
Если на любом этапе баланс становится отрицательным, и его нельзя компенсировать изменением свободных символов, строка не может быть сделана валидной.
Читать дальше →
1 ответ
Сегодня мы разберём задачу 916. Word Subsets.
📝 Описание задачи
Вам даны два массива строк words1 и words2.
Задача: найти все строки из words1, которые являются универсальными относительно всех строк из words2.
Условие универсальности:
Строка a из words1 универсальна, если для каждой строки b из words2 строка b является подмножеством строки a (Подмножество строки: строка b является подмножеством строки a, если каждая буква в b встречается в a как минимум столько же раз).
Пример:
["warrior", "world"] и ["wrr"]
Ответ: ["warrior"], так как только warrior покрывает все буквы из wrr.
💡 Идея
Для эффективного решения задачи:
- Определим максимальное количество вхождений каждой буквы по всем строкам из words2.
- Для каждой строки из words1 проверим, удовлетворяет ли она этим требованиям.
🔍 Детали подхода
Читать дальше →
ответить
Задача на сегодня 2381. Shifting Letters II - решается несложно, но используемая идея мне лично кажется интересной и симпатичной.
Описание задачи 🔎
Дана строка s и список операций shifts, где каждая операция задаёт начало и конец диапазона, а также направление (вперёд или назад).
Ваша задача — применить все сдвиги к строке и вернуть окончательный результат.
Идея 🔄
Для оптимизации решения и избежания повторных расчётов сдвигов, мы используем алгоритм, основанный на префиксных суммах. Это позволяет эффективно сохранять кумулятивный эффект от всех сдвигов в отдельном массиве и применять их конечному результату за один проход.
Детали решения 📝
- Создадим массив
net_shifts, где будут храниться чистые значения сдвигов для каждой позиции в строке.
- Пройдемся по всем операциям и обновим массив
net_shifts, добавляя значения в начале диапазона и вычитая их сразу после его окончания.
- Произведем один последовательный проход по строке, вычисляя кумулятивные сдвиги и применяя их для каждого символа.
Асимптотика ⏳
- Время:
O(n + m), где n — длина строки, m — количество операций.
- Память:
O(n) для массива net_shifts.
Читать дальше →
ответить
Наша очередная задача - 1930. Unique Length-3 Palindromic Subsequences.
📝 Описание задачи
Дана строка s. Необходимо определить количество уникальных палиндромов длины 3, которые являются подпоследовательностями строки.
Подпоследовательность — это строка, полученная из исходной строки удалением некоторых (возможно, нуля) символов без изменения их порядка. Например, для строки "abcde" строка "ace" является подпоследовательностью.
Палиндром — это строка, которая читается одинаково в прямом и обратном направлениях.
💡 Идея
Основная идея заключается в том, что палиндром длины 3 определяется первыми и последними символами, которые совпадают, а также любым допустимым символом посередине.
Мы можем эффективно отслеживать такие пары (первый и последний символы) с помощью битового массива (bitset), что позволяет минимизировать использование памяти.
🔍 Детали подхода
- Массивы частот:
prefix_frequency: хранит частоты символов слева от рассматриваемого.suffix_frequency: хранит частоты символов справа от рассматриваемого.
Читать дальше →
ответить
Следуюшая задача для нашего разбора: 2270. Number of Ways to Split Array.
Описание задачи 📝
Дан массив целых чисел nums длины n. Требуется найти количество индексов i, где выполняются следующие условия:
- Сумма первых
i+1 элементов массива больше или равна сумме оставшихся элементов.
- Индекс
i удовлетворяет 0≤i<n−1, то есть правая часть должна содержать хотя бы один элемент.
Идея 💡
Вместо того чтобы каждый раз вычислять суммы левой и правой частей массива, мы используем баланс для их трекинга.
Изначально баланс равен −total_sum, где total_sum — сумма всех элементов массива. На каждом шаге баланс обновляется с помощью текущего элемента, а проверка условий выполняется через простое сравнение баланса с нулём.
Подробности подхода 🛠️
- Вычислить сумму всех элементов массива и сохранить её в
total_sum.
- Проитерироваться по массиву до предпоследнего элемента:
- Обновить баланс, добавляя
2×текущий элемент.
- Если баланс становится больше или равен нулю, увеличивать счётчик допустимых разбиений.
- Вернуть итоговый счётчик, который отражает количество валидных разбиений.
Читать дальше →
ответить
Следующая наша задача - 2559. Count Vowel Strings in Ranges.
📝 Описание задачи
Нам дан массив строк words и массив запросов queries, где каждый запрос задаётся парой [li, ri]. Необходимо для каждого запроса определить количество строк из диапазона [li, ri], которые начинаются и заканчиваются на гласные буквы ('a', 'e', 'i', 'o', 'u').
Вернуть массив ответов, где каждый элемент соответствует результату очередного запроса.
💡 Идея
Чтобы эффективно отвечать на диапазонные запросы, мы можем заранее подсчитать кумулятивные суммы валидных строк (начинающихся и заканчивающихся на гласные) в массиве префиксных сумм. Это позволяет сократить обработку каждого запроса до константного времени.
🔍 Подробности подхода
- Создание префиксных сумм:
- Сначала создаём итератор
prefix_sum_iter, вычисляющий кумулятивное количество "валидных" строк
(неплохой повод воспользоваться для этого методом std::iter::scan).
- Добавляем
0 в начало итогового массива (см. std::iter::once и std::iter::chain), чтобы упростить расчёты для запросов (исключая лишнюю проверку условий для обработки начала диапазона).
Читать дальше →
ответить
Первая задача в этом году - 1422. Maximum Score After Splitting a String несложная, и интересно решить её за один проход по массиву.
📋 Описание задачи
Дана бинарная строка, состоящая из символов 0 и 1.
Требуется найти максимальный результат разбиения строки на две непустые подстроки.
Результат определяется как:
Результат = (Количество нулей в левой подстроке) + (Количество единиц в правой подстроке).
💡 Идея
Для эффективного решения задачи:
- Рассчитаем динамический баланс для каждого допустимого разбиения строки. Баланс показывает, насколько выгодно разделить строку в конкретной точке.
- Пройдем по строке, обновляя текущий баланс и максимальный результат. Пропустим последнюю итерацию, чтобы обе подстроки оставались непустыми.
🔍 Подробности подхода
- Формула результата: Для разбиения в точке
i:
Result = zero_count + (total_ones - ones_count)
, где:
zero_count – число нулей слева
Читать дальше →
ответить
Последняя в уходящем году задача 983. Minimum Cost For Tickets требует от нас несложного сочетания техник динамического программирования и скользящего окна.
📜 Условие задачи
У вас есть запланированные дни поездок в течение года, указанные в массиве days. Билеты можно приобрести по следующим ценам:
- Однодневный билет за
costs[0] долларов.
- Семидневный билет (покрывает любые последовательно идущие 7 дней) за
costs[1] долларов.
- Тридцатидневный билет (покрывает любые последовательно идущие 30 дней) за
costs[2] долларов.
Необходимо определить минимальные затраты, чтобы покрыть все дни из списка days.
💡 Идея
Для минимизации затрат можно использовать динамическое программирование.
Основная идея — поочередно вычислять минимальную стоимость для каждой даты из массива days, учитывая разные виды билетов, а также использовать индексы скользящих окон для эффективного вычисления диапазонов покрытия билетов.
🛠️ Детали подхода
- Создаем массив
dp, где dp[i] хранит минимальную стоимость поездок для первых i дней.
Читать дальше →
ответить
Сегодня нас опять радует задачка на методы динамического программирования - 2466. Count Ways To Build Good Strings.
😊 Описание задачи
Нам нужно подсчитать количество "хороших строк", длина которых находится в диапазоне [low, high].
Хорошая строка создаётся из пустой строки путём выполнения следующих операций:
- Добавление символа
'0' ровно zero раз.
- Добавление символа
'1' ровно one раз.
Результат может быть очень большим, поэтому необходимо вернуть его по модулю 10⁹+7.
💡 Идея
Для решения задачи мы используем динамическое программирование.
Каждое состояние dp[length] хранит количество способов построить строку длины length.
Постепенно вычисляя значения для всех длин от 1 до high, мы получаем итоговый результат.
🔍 Подробности подхода
- Инициализация:
- Создаём массив
dp длиной high+1, где dp[length] будет содержать количество способов построить строку длины length.
- Базовый случай:
dp[0] = 1, так как существует ровно один способ создать пустую строку.
Читать дальше →
ответить
Задача - 1639. Number of Ways to Form a Target String Given a Dictionary
🔍 Описание задачи
Дано: список строк words одинаковой длины и строка target.
Цель: определить, сколькими способами можно собрать строку target, следуя правилам:
- В очередной шаг можно использовать символ, совпадающий с необходимым очередным символом
target, из любой допустимой позиции таблицы words.
- После выбора символа из определённой позиции все символы всех слов левее или равные этой позиции становятся недоступными.
- Вернуть количество способов по модулю
1_000_000_007
💡 Идея
Мы можем использовать подход динамического программирования. Для быстрого обновления состояний ДП предварительно подсчитаем частоты символов для каждой позиции в words.
Формула ДП:
Пусть dp[i][j] — количество способов собрать первые i символов строки target, используя первые j-й позиции в строках words. Тогда:
dp[i][j] = dp[i][j−1] + dp[i−1][j−1]⋅freqj(target[i]]), где:
Читать дальше →
ответить
Новая задача - 689. Maximum Sum of 3 Non-Overlapping Subarrays.
Описание задачи 📜
Дано: массив чисел nums и целое число k.
Задача: найти три непересекающихся подмассива длины k с максимальной суммой и вернуть индексы их начала.
Если существует несколько решений, вернуть лексикографически минимальное.
Идея 💡
Для нахождения оптимального решения нам нужно:
- Вычислить суммы всех подмассивов длины
k с помощью техники скользящего окна.
- Найти лучшие индексы подмассивов для правой, средней и левой частей массива, используя динамическое программирование.
Это позволяет эффективно комбинировать результаты и найти оптимальное выделение трёх подмассива.
Детали подхода 🛠️
-
Скользящее окно для вычисления сумм:
- Вычисляем суммы всех подмассивов длины
k, чтобы избежать повторных расчетов.
-
Поиск лучших правых подмассивов:
- Сканируем массив справа налево, чтобы сохранить индексы подмассивов с максимальной суммой для каждого положения.
Читать дальше →
ответить
Следующая наша задача - 1014. Best Sightseeing Pair.
Описание задачи 📝
Дано: массив values, где
values[i] — это ценность туристической достопримечательности,j-i — расстояние между двумя достопримечательностями i и j.
Требуется: найти пару достопримечательностей (i < j) с максимальной совместной ценностью по формуле:
score = values[i] + values[j] + i − j
Идея 💡
Основная задача заключается в оптимизации вычислений. Если переписать формулу как:
score = (values[i] + i) + (values[j] − j),
то видно, что для эффективного решения нужно поддерживать максимум для values[j]−j во время итерации.
Это позволяет избежать вложенных циклов и сократить сложность до O(n).
Детали подхода 🛠️
- Используем обратный обход массива с помощью
.enumerate().rev().
- На каждой итерации:
- Вычисляем текущую наилучшую ценность:
score = values[i] + i + max_right,
Читать дальше →
ответить
Сегодня нам предстоит решить задачу 494. Target Sum.
Описание задачи 📜
Нам дана последовательность чисел nums и целевая сумма target.
Необходимо определить количество способов поставить знаки + или - перед числами так, чтобы выражение из всех чисел дало в результате target.
Пример
Для nums = [1, 1, 1, 1, 1] и target = 3, всего 5 правильных комбинаций:
-1+1+1+1+1+1-1+1+1+1+1+1-1+1+1+1+1+1-1+1+1+1+1+1-1
Идея 💡
Эту задачу можно свести к известной задаче о рюкзаке:
-
Разделим числа на две группы:
Sum_Positive — сумма чисел со знаком +,Sum_Negative — сумма чисел со знаком -.
-
Из уравнений:
Sum_Positive − Sum_Negative = Target
Читать дальше →
ответить
Очередная наша задача - 2471. Minimum Number of Operations to Sort a Binary Tree by Level
🚀 Описание задачи
Дано бинарное дерево. На каждом уровне дерева нужно отсортировать значения узлов в строго возрастающем порядке, минимизируя количество операций. За одну операцию можно поменять значения двух узлов одного уровня местами.
🧠 Идея
Для решения задачи:
1. Выполним обход дерева по уровням и соберем значения узлов для каждого уровня.
2. Для каждого уровня определим минимальное количество перестановок, необходимых для сортировки значений, используя алгоритм обнаружения циклов.
📋 Подробности подхода
-
Сбор уровней:
- Используем
std::iter::successors для выполнения обхода дерева по уровням.
- На каждом шаге собираем значения текущего уровня и формируем следующий уровень из дочерних узлов.
-
Минимальные перестановки:
- Для каждого уровня создаем массив индексов, отсортированный по значениям.
- Используя алгоритм обнаружения циклов, подсчитываем минимальное количество операций для приведения массива к упорядоченному состоянию.
Читать дальше →
ответить
Задача: 2940. Find Building Where Alice and Bob Can Meet
Описание задачи 📝
У нас есть массив heights, где heights[i] представляет высоту здания i.
Также даны запросы в виде массива queries, где каждый запрос [ai,bi>] требует определить самое левое здание, на которое могут попасть Алиса и Боб, начав с ai и bi соответственно, при соблюдении следующих условий:
- Алиса и Боб могут двигаться только в здания с индексами больше их текущего.
- Они могут перейти только на здания с высотой больше их текущей.
Если подходящее здание невозможно найти, результат для данного запроса равен −1.
Идея 💡
Мне сходу не известна эффективная структура данных для онлайн-разрешения запросов.
Но можно поступить хитрее, а именно:
- Немедленно обработать "простые" запросы, где результат очевиден.
- Для сложных запросов использовать технику отложенной обработки:
- Сначала отсортировать их по индексу правого здания.
- Затем разрешать запросы, итерируясь по зданиям, и, храня кандидатов на разрешение в двоичной куче.
Читать дальше →
ответить
Задача: 2872. Maximum Number of K-Divisible Components
Описание задачи 📋
Дано неориентированное дерево с n узлами, пронумерованными от 0 до n−1. Также даны:
- массив рёбер edges, где каждое ребро связывает два узла,
- массив значений values, где значение values[i] связано с узлом i,
- число k.
- гарантируется, что сумма всех значений values кратна k
Необходимо найти максимальное количество компонентов, на которые можно разделить дерево, удаляя рёбра, чтобы сумма значений в каждом компоненте делилась на k.
Идея 💡
Будем разбивать дерево на компоненты рекурсивно (DFS), начиная с произвольного узла.
Несложно показать, что родительская вершина должна быть в одной компененте со всеми дочерними, для которых сумма значений в соответствующем поддереве не делится на k.
Детали подхода 🚀
-
Построение графа:
- Представляем дерево в виде списка смежности для удобного обхода.
-
Обход дерева:
Читать дальше →
ответить
На нашей новой задаче 2415. Reverse Odd Levels of Binary Tree есть повод продемонстировать продвинутые методы Rust работы с итераторами (std::iter::successors & std::iter::zip), а также "непристойную" работу c реф-каунт ячейками :(
📜 Описание задачи
Дано идеальное бинарное дерево. Требуется изменить порядок значений узлов на всех нечетных уровнях дерева.
Идеальное дерево — это дерево, где у каждого узла два потомка, а все листья находятся на одном уровне.
💡 Идея
Мы адаптируем BFS для обхода дерева по уровням. На каждом уровне проверяется, нужно ли инвертировать порядок значений (для нечетных уровней). С помощью вспомогательной функции формируются следующие уровни дерева.
📋 Подробности подхода
-
Вспомогательная функция
next_level:
- Формирует следующий уровень дерева, собирая всех левых и правых потомков текущих узлов.
-
Завершение обработки:
- Проверка, что текущий уровень является листовым, выполняется через условие
nodes[0].borrow().left.is_none().
- При достижении уровня листьев обработка завершается.
-
Обход уровней с помощью
std::iter::successors:
- Используется функциональный подход для последовательного формирования уровней дерева. Итератор автоматически останавливается при достижении листового уровня.
Читать дальше →
ответить
Для задачи 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
}
}
Сегодняшняя задача 1475. Final Prices With a Special Discount in a Shop решается с помощью стандартного стека, но интересно и нестандартно выглядит мотивация его использования.
Описание задачи 🛒
У вас есть массив цен prices, где prices[i] — это цена i-го товара. Если вы покупаете товар i, вы можете получить скидку, равную цене первого товара с индексом j>i, для которого выполняется условие prices[j] ≤ prices[i]. Если такого товара нет, скидка не применяется. Требуется вернуть массив, где каждая позиция показывает финальную цену с учётом скидки.
Идея 🤔
- Мы идём по массиву цен и обрабатываем товары по порядку.
- Для каждого товара находим, для каких товаров он определяет скидку, проверяя необработанные товары с индексами слева, чья цена больше или равна текущей.
- Чтобы эффективно отслеживать эти необработанные товары, используем монотонный стек. Этот стек хранит индексы товаров, цены которых упорядочены по возрастанию. Это позволяет быстро находить и применять скидки.
Подход 🚀
- Создаём стек
discount_candidates, чтобы хранить индексы товаров, ожидающих применения скидки.
- Итерируем по массиву
prices:
- Пока верхний элемент стека соответствует условию скидки (
цена товара в стеке ≥ текущей цене), применяем скидку и удаляем элемент из стека.
Читать дальше →
ответить
Страница
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
