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

🟢   🔖  栈 数组 单调栈  🔗 力扣 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 最终需要支付的价格。

解题思路

可以通过 单调栈 的方法高效解决这道题。

• 使用一个栈存储元素的索引，确保栈内的价格值按 递增顺序 排列。
• 每次遇到一个新元素时，检查栈顶元素是否大于等于当前值。如果是，就弹出栈顶元素并更新对应位置的价格。
• 对于每个元素，尝试找到右侧第一个小于等于它的元素。如果找到，则更新价格；如果找不到，保持原值。

1. 初始化栈：栈 stack 用来存储价格的索引。

2. 遍历数组：

   • 遍历 prices 数组中的每个元素。
   • 当栈不为空且当前价格小于等于栈顶对应的价格时：
     • 弹出栈顶索引 top。
     • 更新 prices[top] = prices[top] - prices[i]。
   • 将当前索引压入栈中。

3. 返回结果：遍历完成后，prices 数组已经被修改，直接返回即可。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 prices 的长度，每个元素最多进栈一次，出栈一次。
• 空间复杂度：O(n)，最坏情况下栈中存储所有的元素索引。

代码

/**
 * @param {number[]} prices
 * @return {number[]}
 */
var finalPrices = function (prices) {
	let stack = []; // 单调栈
	for (let i = 0; i < prices.length; i++) {
		// 检查栈顶元素是否大于等于当前价格
		while (stack.length > 0 && prices[stack[stack.length - 1]] >= prices[i]) {
			// 更新栈顶索引对应的价格
			prices[stack.pop()] -= prices[i];
		}
		// 当前索引入栈
		stack.push(i);
	}
	return prices;
};