Задача. Цена со скидкой

Задача. Дан целочисленный массив prices, где prices[i] - цена i-го товара в магазине. На товары действует специальная скидка. Если вы купите i-й товар, то получите скидку, равную prices[j], где j - минимальный индекс, такой, что j > i и prices[j] <= prices[i]. В противном случае скидка не предоставляется.

Необходимо вернуть массив, где output[i] - конечная цена, которую вы заплатите за i-й товар магазина с учетом скидки.

Пример

prices = [8,4,6,2,3]

Output: [4,2,4,2,3]

Примечание:

• 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.

Разбор

Задачу можно сделать в лоб и выполнить проход по массиву с вложенным циклом. Однако, мы можем воспользоваться стеком, а в стеке хранить цены, для которых мы еще не нашли специальную скидку.

Алгоритм

1. Создадим стек, где элементы стека будут индексы элементов массива.
2. Проходим по массиву цен.
3. Внутри основного цикла пройдемся по элементам стека, где prices[stack.Peek()] >= prices[i]. То есть элемент стека должен быть больше, чем текущий элемент массива, т.к. только в этом случае мы можем применить спец.скидку.
   - Если мы можем применить спец.скидку, то вычитаем эту скидку из элемента стека.
4. После прохода по элементам стека, добавляем текущий индекс в стек.
5. После прохода по всем элементам массива мы получим массив цен со спец.скидкой.
   

https://gist.github.com/unilecs/61bab8a60cdcf478d8e0493ca8121b7c

Play-test

https://dotnetfiddle.net/ccrmc1