commit c4a8b500bf5d89f59e1fa436d56897c29cad0094 parent fb2343cec8a97bf5b6dcef7feb846d3fc2a5a620 Author: Dimitrije Dobrota <mail@dimitrijedobrota.com> Date: Wed, 18 Dec 2024 17:30:05 +0100 Daily Problem Diffstat:
| A | Problems/1475.cpp | | | 37 | +++++++++++++++++++++++++++++++++++++ |
| M | README.md | | | 1 | + |
2 files changed, 38 insertions(+), 0 deletions(-)
diff --git a/Problems/1475.cpp b/Problems/1475.cpp @@ -0,0 +1,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; + } +}; diff --git a/README.md b/README.md @@ -944,6 +944,7 @@ reference and a base for solving problems. | 1470 | Easy | [Shuffle the Array](Problems/1470.cpp) | | 1471 | Medium | [The k Strongest Values in an Array](Problems/1471.cpp) | | 1472 | Medium | [Design Browser History ](Problems/1472.cpp) | +| 1475 | Easy | [Final Prices With a Special Discount in a Shop](Problems/1475.cpp) | | 1476 | Medium | [Subrectangle Queries](Problems/1476.cpp) | | 1480 | Easy | [Running Sum of 1d Array](Problems/1480.cpp) | | 1481 | Medium | [Least Number of Unique Integers after K Removals](Problems/1481.cpp) |