Java?C++?算法題解leetcode145商品折扣后最終價格單調(diào)棧

更新時間：2022年09月14日 10:11:06 作者：AnjaVon

這篇文章主要介紹了Java?C++?算法題解leetcode145商品折扣后最終價格單調(diào)棧示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路一：暴力模擬

由于數(shù)據(jù)范圍不算離譜，所以直接遍歷解決可行。

Java

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int discount = 0;
            for (int j = i + 1; j < n && discount == 0; j++) {
                if (prices[j] <= prices[i])
                    discount = prices[j];
            }                
            res[i] = prices[i] - discount;
        }
        return res;
    }
}

時間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(n)

C++

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            int discount = 0;
            for (int j = i + 1; j < n && discount == 0; j++) {
                if (prices[j] <= prices[i])
                    discount = prices[j];
            }
            res[i] = prices[i] - discount;
        }
        return res;
    }
};

時間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(n)

Rust

impl Solution {
    pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
        let n = prices.len();
        let mut res = vec![0;n];
        (0..n).for_each(|i| {
            res[i] = prices[i] - ((i + 1)..n).find(|&j| prices[j] <= prices[i]).map_or(0, |j| prices[j]);
        });
        res
    }
}

遍歷存每次的count，最后再遍歷計算得出結(jié)果

impl Solution {
    pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
        let n = prices.len();
        let mut discount = vec![0;n];
        for j in 1..n {
            for i in 0..j {
                if discount[i] == 0 && prices[j] <= prices[i] {
                    discount[i] = prices[j];
                }
            }
        }
        prices.iter().zip(discount.iter()).map(|(&x, &y)| x - y).collect::<Vec<i32>>()
    }
}

時間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(n)

思路二：單調(diào)棧

是個逆向思維，不考慮誰是我的折扣，而去考慮我可以是誰的折扣。已知的一個prices[j]只能折扣其左邊最近的幾個大于它的值，按這個思路分析單調(diào)和棧：
- 從前向后依次遍歷prices，遇到需要打折的商品，將其下標(biāo)放入一個容器：
  - 若當(dāng)前處理值小于末尾，那么它就可以作為末尾元素的折扣【因為它是末尾元素后面第一個小于它的值】，將末尾元素取出、折扣、放入已折扣數(shù)組（即結(jié)果數(shù)組），一直重復(fù)到容器末尾元素小于當(dāng)前處理值，則將當(dāng)前處理值放入容器【為避免該值不可打折造成缺漏，此時將其價格同步至已折扣數(shù)組】。
  - 若當(dāng)前處理的值高于容器內(nèi)的值，那么它不能作為里面任何一者的折扣，因此直接加入容器。
- 由此可知，加入容器值會大于容器內(nèi)的其它值，該容器是單調(diào)遞增的。此外，處理的一直是容器末尾的元素，添加也是直接補在末尾，所以符合棧的結(jié)構(gòu)。

Java

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] res = new int[n]; // 已打折價格
        Deque<Integer> sta = new ArrayDeque<>(); // 待打折下標(biāo)
        for (int i = 0; i < n; i++) {
            while (!sta.isEmpty() && prices[sta.peekLast()] >= prices[i]) {
                int idx = sta.pollLast();
                res[idx] = prices[idx] - prices[i];
            }
            sta.addLast(i); // 最高
            res[i] = prices[i];
        }
        return res;
    }
}

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

C++

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> res(n); // 已打折價格
        stack<int> sta; // 待打折下標(biāo)
        for (int i = 0; i < n; i++) {
            while (!sta.empty() && prices[sta.top()] >= prices[i]) {
                int idx = sta.top();
                sta.pop();
                res[idx] = prices[idx] - prices[i];
            }
            sta.push(i); // 最高
            res[i] = prices[i];
        }
        return res;
    }
};

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

Rust

impl Solution {
    pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
        let n = prices.len();
        let mut res = vec![0;n]; // 已打折價格
        let mut sta = vec![]; // 待打折下標(biāo)
        for i in 0..n {
            while let Some(&idx) = sta.last() {
                if prices[idx] < prices[i] {
                    break;
                }
                sta.pop();
                res[idx] = prices[idx] - prices[i];
            }
            sta.push(i); // 最高
            res[i] = prices[i];
        }
        res
    }
}