Java C++ 算法题解leetcode145商品折扣后最终价格单调栈
目录
- 题目要求
- 思路一:暴力模拟
- Java
- C++
- Rust
- 思路二:单调栈
- Java
- C++
- Rust
题目要求
思路一:暴力模拟
- 由于数据范围不算离谱,所以直接遍历解决可行。
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,遇到需要打折的商品,将其下标放入一个容器:
- 若当前处理值小于末尾,那么它就可以作为末尾元素的折扣【因为它是末尾元素后面第一个小于它的值】,将末尾元素取出、折扣、放入已折扣数组(即结果数组),一直重复到容器末尾元素小于当前处理值,则将当前处理值放入容器【为避免该值不可打折造成缺漏,此时将其价格同步至已折扣数组】。
- 若当前处理的值高于容器内的值,那么它不能作为里面任何一者的折扣,因此直接加入容器。
- 由此可知,加入容器值会大于容器内的其它值,该容器是单调递增的。此外,处理的一直是容器末尾的元素,添加也是直接补在末尾,所以符合栈的结构。
- 从前向后依次遍历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)
以上就是Java C++ 算法题解leetcode145商品折扣后最终价格单调栈的详细内容,更多关于Java C++ 商品折扣后价格的资料请关注我们其它相关文章!
赞 (0)