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

链接：1475.商品折扣后的最终价格
难度：Easy
标签：栈、数组、单调栈
简介：请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

题解 1 - cpp

• 编辑时间：2022-09-01
• 内存消耗：2.1MB
• 编程语言：cpp
• 解法介绍：单调栈。

impl Solution {
    pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
        let mut s = Vec::<usize>::new();
        let mut prices = prices;
        for i in 0..prices.len() {
            while !s.is_empty() && prices[*s.last().unwrap()] >= prices[i] {
                let prev = s.pop().unwrap();
                prices[prev] -= prices[i];
            }
            s.push(i);
        }
        prices
    }
}

题解 2 - cpp

• 编辑时间：2022-09-01
• 执行用时：4ms
• 内存消耗：9.8MB
• 编程语言：cpp
• 解法介绍：单调栈。

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