跳至主要內容

1475. 商品折扣后的最终价格


1475. 商品折扣后的最终价格open in new window

🟢   🔖  数组 单调栈  🔗 力扣open in new window LeetCodeopen in new window

题目

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;
};