leetcode

0 // Brute Force

1 class Solution {

2 public:

3 vector<int> finalPrices(vector<int> &prices) const {

4 const int n = size(prices);

5

6 for (int i = 0; i < n; i++) {

7 for (int j = i + 1; j < n; j++) {

8 if (prices[j] > prices[i]) continue;

9 prices[i] -= prices[j];

10 break;

11 }

12 }

13

14 return prices;

15 }

16 };

17

18 // Monotonic Stack

19 class Solution {

20 public:

21 vector<int> finalPrices(vector<int> &prices) const {

22 const int n = size(prices);

23 stack<int> st;

24

25 for (int i = 0; i < n; i++) {

26 while (!st.empty() && prices[st.top()] >= prices[i]) {

27 prices[st.top()] -= prices[i];

28 st.pop();

29 }

30

31 st.push(i);

32 }

33

34 return prices;

35 }

36 };