1475. 商品折扣後的最終價格

思路

每一個商品的位置應該減去距離自己最近，且價格小於等於自己的商品。
建立一個棧，記錄數字的位置，並在整個過程當中保持單調。
比如 $[8,4,6,2,3]$，

• 加入數字 $8$，stk = [8]。
• 加入數字 $4$，他會把前面比自己大的數字重棧中彈出，
  對被彈出的數字 $8$ 來說，$4$ 就是最近的小於等於自己的數字，最後stk = [4]。
• 加入數字 $6$，stk = [4,6]。
• 加入數字 $2$，彈出比自己小的數字，對被彈出的數字來說，當前數字 $2$ 是目標，最後stk = [2]。
• 加入數字 $3$，stk = [2,3]。

程式碼

單調棧

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> stk;
        for(int i = 0; i < n; ++i) {
            while(!stk.empty() && prices[stk.back()] >= prices[i]) {
                // 被 pop 出來的數字，對它來說，當前位置的價格是最近的 <= 自己的數字。
                prices[stk.back()] -= prices[i]; 
                stk.pop_back();
            }
            stk.push_back(i);
        }
        return prices;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$