leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1475.cpp (817B)

      1 // Brute Force
      2 class Solution {
      3   public:
      4     vector<int> finalPrices(vector<int> &prices) const {
      5         const int n = size(prices);
      6 
      7         for (int i = 0; i < n; i++) {
      8             for (int j = i + 1; j < n; j++) {
      9                 if (prices[j] > prices[i]) continue;
     10                 prices[i] -= prices[j];
     11                 break;
     12             }
     13         }
     14 
     15         return prices;
     16     }
     17 };
     18 
     19 // Monotonic Stack
     20 class Solution {
     21   public:
     22     vector<int> finalPrices(vector<int> &prices) const {
     23         const int n = size(prices);
     24         stack<int> st;
     25 
     26         for (int i = 0; i < n; i++) {
     27             while (!st.empty() && prices[st.top()] >= prices[i]) {
     28                 prices[st.top()] -= prices[i];
     29                 st.pop();
     30             }
     31 
     32             st.push(i);
     33         }
     34 
     35         return prices;
     36     }
     37 };