Problem 1475. 商品折扣后的最终价格

思路：单调栈模板题，注意题目要求

Accode:

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        stack<int> sta;
        vector<int> ans(prices.size());
        for(int i=0;i<prices.size();i++){
            while(sta.size() && prices[sta.top()]>=prices[i]){
                ans[sta.top()] = prices[sta.top()] - prices[i];
                sta.pop();
            }
            sta.push(i);
        }
        while(sta.size()){
            ans[sta.top()] = prices[sta.top()];
            sta.pop();
        }
        return ans;
    }
};

时间复杂度：$o(n)$