leetcode/Problems/1475.cpp at master · DimitrijeDobrota/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Brute Force
class Solution {
  public:
    vector<int> finalPrices(vector<int> &prices) const {
        const int n = size(prices);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (prices[j] > prices[i]) continue;
                prices[i] -= prices[j];
                break;
            }
        }

        return prices;
    }
};

// Monotonic Stack
class Solution {
  public:
    vector<int> finalPrices(vector<int> &prices) const {
        const int n = size(prices);
        stack<int> st;

        for (int i = 0; i < n; i++) {
            while (!st.empty() && prices[st.top()] >= prices[i]) {
                prices[st.top()] -= prices[i];
                st.pop();
            }

            st.push(i);
        }

        return prices;
    }
};