leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1475.cpp (817B)

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 };