Задачи
October 9, 2023
Задача. Цена со скидкой
Задача. Дан целочисленный массив prices, где prices[i] - цена i-го товара в магазине. На товары действует специальная скидка. Если вы купите i-й товар, то получите скидку, равную prices[j], где j - минимальный индекс, такой, что j > i и prices[j] <= prices[i]. В противном случае скидка не предоставляется.
Необходимо вернуть массив, где output[i] - конечная цена, которую вы заплатите за i-й товар магазина с учетом скидки.
- 8: скидка равна prices[1] = 4, конечная цена - (8 - 4) = 4;
- 4: скидка равна prices[3] = 2, конечная цена - (4 - 2) = 2;
- 6: скидка равна prices[3] = 2, конечная цена - (6 - 2) = 4;
- 2: скидки нет, т.к. дальше в массиве нет элементов меньше 2.
- 3: скидки нет, т.к. дальше в массиве нет элементов меньше 3.
Разбор
Задачу можно сделать в лоб и выполнить проход по массиву с вложенным циклом. Однако, мы можем воспользоваться стеком, а в стеке хранить цены, для которых мы еще не нашли специальную скидку.
- Создадим стек, где элементы стека будут индексы элементов массива.
- Проходим по массиву цен.
- Внутри основного цикла пройдемся по элементам стека, где prices[stack.Peek()] >= prices[i]. То есть элемент стека должен быть больше, чем текущий элемент массива, т.к. только в этом случае мы можем применить спец.скидку.
- Если мы можем применить спец.скидку, то вычитаем эту скидку из элемента стека. - После прохода по элементам стека, добавляем текущий индекс в стек.
- После прохода по всем элементам массива мы получим массив цен со спец.скидкой.
https://gist.github.com/unilecs/61bab8a60cdcf478d8e0493ca8121b7c