Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

题目要求

思路一：暴力模拟

• 由于数据范围不算离谱，所以直接遍历解决可行。

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;
   }
}

• 时间复杂度：O(n^2)

• 空间复杂度：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;
   }
};

• 时间复杂度：O(n^2)

• 空间复杂度：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，最后再遍历计算得出结果

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>>()
   }
}

• 时间复杂度：O(n^2)

• 空间复杂度：O(n)

思路二：单调栈

• 是个逆向思维，不考虑谁是我的折扣，而去考虑我可以是谁的折扣。已知的一个prices[j]只能折扣其左边最近的几个大于它的值，按这个思路分析单调和栈：

• 若当前处理值小于末尾，那么它就可以作为末尾元素的折扣【因为它是末尾元素后面第一个小于它的值】，将末尾元素取出、折扣、放入已折扣数组（即结果数组），一直重复到容器末尾元素小于当前处理值，则将当前处理值放入容器【为避免该值不可打折造成缺漏，此时将其价格同步至已折扣数组】。

• 若当前处理的值高于容器内的值，那么它不能作为里面任何一者的折扣，因此直接加入容器。

• 从前向后依次遍历prices，遇到需要打折的商品，将其下标放入一个容器：

• 由此可知，加入容器值会大于容器内的其它值，该容器是单调递增的。此外，处理的一直是容器末尾的元素，添加也是直接补在末尾，所以符合栈的结构。

Java

class Solution {
   public int[] finalPrices(int[] prices) {
       int n = prices.length;
       int[] res = new int[n]; // 已打折价格
       Deque<Integer> sta = new ArrayDeque<>(); // 待打折下标
       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;
   }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

C++

class Solution {
public:
   vector<int> finalPrices(vector<int>& prices) {
       int n = prices.size();
       vector<int> res(n); // 已打折价格
       stack<int> sta; // 待打折下标
       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;
   }
};

• 时间复杂度：O(n)

• 空间复杂度：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![]; // 待打折下标
       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
   }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

来源：https://juejin.cn/post/7138321057219346463