Leetcode - 1475. Final Prices With a Special Discount in a Shop

문제

가격이 적혀있는 배열이 주어진다. 현재 index보다 큰 index의 값중에 첫번째 작은가격의 값으로 현재 값을 할인 받는다면 최종 할인된 가격배열은?
가령 아래 예시에서 [0] index의 이후 index중에 [1]의 가격이 4이므로 [0]번의 할인된 가격은 8-4 가 된다.

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. 
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. 
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. 
For items 3 and 4 you will not receive any discount at all.

해결

다음 작은 값을 찾는 문제이므로 Monotonic stack문제, incresing monotonic stack 으로 다음 배열을 찾고 할인가격을 계산.

소요시간 : 18min

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        stack<pair<int, int>> disc; // idx, val
        
        disc.push(make_pair(0, prices[0]));
        for (int cur = 1; cur < prices.size(); cur++) {
            // incresing monotonic stack
            while (!disc.empty() && disc.top().second >= prices[cur]) {
                pair<int, int> check = disc.top();
                disc.pop();
                prices[check.first] -= prices[cur];
            }
            disc.push(make_pair(cur, prices[cur]));
        }
        return prices;
    }
};