# 1475. Final Prices With a Special Discount in a Shop
[1475. Final Prices With a Special Discount in a Shop](https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/) (<font color="#00AF9B"> Easy</font> 通過率: 80.8%)

## 限制條件
<ul>
<li>1 <= prices.length <= 500</li>
<li>1 <= prices[i] <= 1000</li>
</ul>

### 解法 1
第一種方法使用暴力法，以 O(n^2) 的方式去尋找某個數字後面有沒有比自己小的數字，有的話這個數字會減去找到的這個數的數值

簡單，但很慢

- 時間複雜度: $O(N^2)$
- 空間複雜度: $O(1)$

class Solution {
public:
    int findSmallerIndex(vector<int>& nums, int index) {
        for (int i = index + 1; i < nums.size(); i++) {
            if (nums[index] >= nums[i]) {
                return i;
            }
        }
        return index;
    }
    vector<int> finalPrices(vector<int>& prices) {
        for (int i = 0; i < prices.size(); i++) {
            int index = findSmallerIndex(prices, i);
            if (index != i)
                prices[i] -= prices[index];
        }

        return prices;
    }
};

### 解法 2
第二種方法使用 [Monotonic Stack](https://medium.com/%E6%8A%80%E8%A1%93%E7%AD%86%E8%A8%98/%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98%E7%B3%BB%E5%88%97-monotonic-stack-queue-5ad1c35a3dfe) 可以降低時間上的浪費

- 時間複雜度: $O(N)$
- 空間複雜度: $O(N)$

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        stack<int> st;

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

        return prices;
    }
};