1475. Final Prices With a Special Discount in a Shop

🟢   🔖  栈 数组 单调栈  🔗 LeetCode

题目

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