Сегодняшняя задача 1475. Final Prices With a Special Discount in a Shop решается с помощью стандартного стека, но интересно и нестандартно выглядит мотивация его использования.
Описание задачи 🛒
У вас есть массив цен prices, где prices[i] — это цена i-го товара. Если вы покупаете товар i, вы можете получить скидку, равную цене первого товара с индексом j>i, для которого выполняется условие prices[j] ≤ prices[i]. Если такого товара нет, скидка не применяется. Требуется вернуть массив, где каждая позиция показывает финальную цену с учётом скидки.
Идея 🤔
- Мы идём по массиву цен и обрабатываем товары по порядку.
- Для каждого товара находим, для каких товаров он определяет скидку, проверяя необработанные товары с индексами слева, чья цена больше или равна текущей.
- Чтобы эффективно отслеживать эти необработанные товары, используем монотонный стек. Этот стек хранит индексы товаров, цены которых упорядочены по возрастанию. Это позволяет быстро находить и применять скидки.
Подход 🚀
- Создаём стек
discount_candidates, чтобы хранить индексы товаров, ожидающих применения скидки.
- Итерируем по массиву
prices:
- Пока верхний элемент стека соответствует условию скидки (
цена товара в стеке ≥ текущей цене), применяем скидку и удаляем элемент из стека.
- Добавляем текущий индекс в стек.
- Возвращаем обновлённый массив цен.
Сложность 📊
- Временная сложность:
O(n)
- Каждый элемент добавляется и удаляется из стека не более одного раза.
- Пространственная сложность:
O(n)
- В худшем случае стек может содержать все элементы массива.
Исходный код решения
impl Solution {
pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
let mut result = prices.clone(); // Clone prices to modify and return
let mut discount_candidates: Vec<usize> = Vec::new(); // Stack to store indices of items awaiting discounts
for (idx, price) in prices.into_iter().enumerate() {
// Process the stack to apply discounts where applicable
while let Some(&largest_candidate_index) = discount_candidates.last() {
if result[largest_candidate_index] >= price {
result[largest_candidate_index] -= price; // Apply the discount
discount_candidates.pop(); // Remove from stack
} else {
break; // Stop if the discount condition is not met
}
}
// Add the current index to the stack for future discounts
discount_candidates.push(idx);
}
result
}
}
Замечания
Если вчитаться в ограничения задачи на LeetCode - то заходить должно решение и за O(N³) (что уже больше сложности наивного подхода). Но этот быстрый алгоритм получился достаточно симпатичным на мой взгляд, чтобы интересно было им поделиться :)