百度推广网站备案,网站建站基本要素,万江专业网站快速排名,商业网站建设平台LeetCode-1475. 商品折扣后的最终价格【栈 数组 单调栈】 题目描述#xff1a;解题思路一#xff1a;暴力解法。两层for。解题思路二#xff1a;单调栈#xff0c;具体思路是反向遍历数组prices。遇到栈顶元素小于当前元素的就出栈#xff0c;目的是为了找到当前位置右边的… LeetCode-1475. 商品折扣后的最终价格【栈 数组 单调栈】 题目描述解题思路一暴力解法。两层for。解题思路二单调栈具体思路是反向遍历数组prices。遇到栈顶元素小于当前元素的就出栈目的是为了找到当前位置右边的第一个小于等于的元素即为栈顶元素。此时我们可以直接遍历一遍得到答案。妙蛙 :smiley: :smiley: :smiley:解题思路三0 题目描述
给你一个数组 prices 其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动如果你要买第 i 件商品那么你可以得到与 prices[j] 相等的折扣其中 j 是满足 j i 且 prices[j] prices[i] 的 最小下标 如果没有满足条件的 j 你将没有任何折扣。
请你返回一个数组数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
示例 1 输入prices [8,4,6,2,3] 输出[4,2,4,2,3] 解释 商品 0 的价格为 price[0]8 你将得到 prices[1]4 的折扣所以最终价格为 8 - 4 4 。 商品 1 的价格为 price[1]4 你将得到 prices[3]2 的折扣所以最终价格为 4 - 2 2 。 商品 2 的价格为 price[2]6 你将得到 prices[3]2 的折扣所以最终价格为 6 - 2 4 。 商品 3 和 4 都没有折扣。
示例 2 输入prices [1,2,3,4,5] 输出[1,2,3,4,5] 解释在这个例子中所有商品都没有折扣。
示例 3 输入prices [10,1,1,6] 输出[9,0,1,6]
提示 1 prices.length 500 1 prices[i] 10^3
解题思路一暴力解法。两层for。
class Solution:def finalPrices(self, prices: List[int]) - List[int]:ans []n len(prices)for i in range(n-1):flag 1for j in range(i1,n,1):if prices[i] prices[j]:ans.append(prices[i] - prices[j])flag 0breakif flag: ans.append(prices[i])ans.append(prices[n-1])return ans时间复杂度O(n2) 空间复杂度O(1)
解题思路二单调栈具体思路是反向遍历数组prices。遇到栈顶元素小于当前元素的就出栈目的是为了找到当前位置右边的第一个小于等于的元素即为栈顶元素。此时我们可以直接遍历一遍得到答案。妙蛙
可以参考LeetCode-496. 下一个更大元素 I【栈 数组 哈希表 单调栈】
class Solution:def finalPrices(self, prices: List[int]) - List[int]:n len(prices)res [0] * nstack []for i in reversed(range(n)):while stack and prices[i] stack[-1]: stack.pop()res[i] prices[i] - stack[-1] if stack else prices[i]stack.append(prices[i])return res时间复杂度O(n) 空间复杂度O(n)栈空间
解题思路三0
