Java实现长尾词的算法，用单调栈如何改写？

本文共计1226个文字，预计阅读时间需要5分钟。

目录+主题要求+思路一：暴力模拟+Java+C+++Rust+思路二：单调栈+Java+C+++Rust+主题要求+思路一：暴力模拟+由于数据范围不算离谱，直接遍历解决即可。+Java+class+Solution+{+public+int%5B%5D+final%E2%80%9D

目录

• 题目要求
• 思路一：暴力模拟
• 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，遇到需要打折的商品，将其下标放入一个容器：
    • 若当前处理值小于末尾，那么它就可以作为末尾元素的折扣，将末尾元素取出、折扣、放入已折扣数组（即结果数组），一直重复到容器末尾元素小于当前处理值，则将当前处理值放入容器。
    • 若当前处理的值高于容器内的值，那么它不能作为里面任何一者的折扣，因此直接加入容器。
  • 由此可知，加入容器值会大于容器内的其它值，该容器是单调递增的。此外，处理的一直是容器末尾的元素，添加也是直接补在末尾，所以符合栈的结构。

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)

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)

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++ 商品折扣后价格的资料请关注自由互联其它相关文章！