1475. 商品折扣后的最终价格
1475. 商品折扣后的最终价格
题目
You are given an integer array prices
where prices[i]
is the price of the ith
item in a shop.
There is a special discount for items in the shop. If you buy the ith
item, then you will receive a discount equivalent to prices[j]
where j
is the minimum index such that j > i
and prices[j] <= prices[i]
. Otherwise, you will not receive any discount at all.
Return an integer array answer
where answer[i]
is the final price you will pay for the ith
item of the shop, considering the special discount.
Example 1:
Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation:
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
For items 3 and 4 you will not receive any discount at all.
Example 2:
Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: In this case, for all items, you will not receive any discount at all.
Example 3:
Input: prices = [10,1,1,6]
Output: [9,0,1,6]
Constraints:
1 <= prices.length <= 500
1 <= prices[i] <= 1000
题目大意
给你一个数组 prices
,其中 prices[i]
是商店里第 i
件商品的价格。
商店里正在进行促销活动,如果你要买第 i 件商品,那么你可以得到与 prices[j]
相等的折扣,其中 j
是满足 j >
i 且 prices[j] <= prices[i]
的 最小下标 ,如果没有满足条件的 j
,你将没有任何折扣。
请你返回一个数组,数组中第 i
个元素是折扣后你购买商品 i
最终需要支付的价格。
解题思路
本题与 第 496 题 思路一样,都可以使用单调栈。
倒序遍历 prices
,并用单调栈中维护当前位置右边的更小的元素列表,从栈底到栈顶的元素是单调递增的。
当遍历第 i
个元素 prices[i]
时:
- 如果当前栈顶的元素大于
prices[i]
,则将栈顶元素出栈,直到栈顶的元素小于等于prices[i]
,栈顶的元素即为右边第一个小于prices[i]
的元素; - 如果当前栈顶的元素小于等于
prices[i]
,此时可以知道当前栈顶元素即为i
的右边第一个小于等于prices[i]
的元素,此时第i
个物品折后的价格为prices[i]
与栈顶的元素的差。 - 如果当前栈中的元素为空,则此时折扣为
0
,商品的价格为原价prices[i]
; - 将
prices[i]
压入栈中,保证prices[i]
为当前栈中的最大值;
代码
/**
* @param {number[]} prices
* @return {number[]}
*/
var finalPrices = function (prices) {
let stack = [];
let res = new Array(prices.length).fill(0);
for (let i = prices.length - 1; i >= 0; i--) {
while (stack.length && stack[stack.length - 1] > prices[i]) {
stack.pop();
}
res[i] =
stack.length === 0 ? prices[i] : prices[i] - stack[stack.length - 1];
stack.push(prices[i]);
}
return res;
};