本文主要是介绍每日一题——LeetCode1475.商品折扣后的最终价格,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
方法一 一次遍历
对于每一个prices[i]找到在他后面且离他最近的更小值prices[j] ,prices[i]-prices[j]就是目标值,
如果不存在这样的prices[j]则直接返回prices[i]
var finalPrices = function(prices) {let res=[]for(let i=0;i<prices.length-1;i++){if(prices[i]-prices[i+1]>=0){res.push(prices[i]-prices[i+1])}else{let j=i+1while(j<prices.length && prices[i]-prices[j]<0){j++}console.log(j)if(j===prices.length){res.push(prices[i])}else{res.push(prices[i]-prices[j])}}}res.push(prices[prices.length-1])return res
};
消耗时间和内存情况:
方法二 单调栈
来源:力扣官方题解
链接:leetcode1475.商品折扣后的最终价格
var finalPrices = function(prices) {const n = prices.length;const ans = new Array(n).fill(0);const stack = [];for (let i = n - 1; i >= 0; i--) {while (stack.length && stack[stack.length - 1] > prices[i]) {stack.pop();}ans[i] = stack.length === 0 ? prices[i] : prices[i] - stack[stack.length - 1];stack.push(prices[i]);}return ans;
};
消耗时间和内存情况:
这篇关于每日一题——LeetCode1475.商品折扣后的最终价格的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!