Easy

题目描述

给你一个整数数组 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] <= 1000

解题思路

解题思路

这道题要求找到每个商品右边第一个价格小于等于它的商品，然后计算折扣后的价格。

方法一：暴力解法

对于每个商品 i，遍历其右边的所有商品，找到第一个价格小于等于 prices[i] 的商品 j，计算折扣后的价格。如果没有找到，则价格不变。时间复杂度 O(n²)，空间复杂度 O(1)。

方法二：单调栈（推荐）

这是一个典型的"下一个更小元素"问题，可以用单调栈高效解决。我们维护一个单调递减的栈，存储商品的索引。

  • 遍历数组，对于当前商品，如果它的价格小于等于栈顶商品的价格，说明找到了栈顶商品的折扣
  • 弹出栈顶并计算折扣后价格，继续检查新的栈顶
  • 将当前商品索引入栈

这种方法时间复杂度 O(n)，每个元素最多入栈出栈一次，空间复杂度 O(n)。

由于题目数据规模较小（n ≤ 500），暴力解法也完全可行，但单调栈解法更优雅且具有更好的时间复杂度。

代码实现

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> result = prices;
        stack<int> st;
        
        for (int i = 0; i < n; i++) {
            while (!st.empty() && prices[st.top()] >= prices[i]) {
                int idx = st.top();
                st.pop();
                result[idx] = prices[idx] - prices[i];
            }
            st.push(i);
        }
        
        return result;
    }
};

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        result = prices[:]
        stack = []
        
        for i in range(n):
            while stack and prices[stack[-1]] >= prices[i]:
                idx = stack.pop()
                result[idx] = prices[idx] - prices[i]
            stack.append(i)
        
        return result

public class Solution {
    public int[] FinalPrices(int[] prices) {
        int n = prices.Length;
        int[] result = new int[n];
        Array.Copy(prices, result, n);
        Stack<int> stack = new Stack<int>();
        
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && prices[stack.Peek()] >= prices[i]) {
                int idx = stack.Pop();
                result[idx] = prices[idx] - prices[i];
            }
            stack.Push(i);
        }
        
        return result;
    }
}

var finalPrices = function(prices) {
    const n = prices.length;
    const result = [...prices];
    const stack = [];
    
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && prices[stack[stack.length - 1]] >= prices[i]) {
            const idx = stack.pop();
            result[idx] = prices[idx] - prices[i];
        }
        stack.push(i);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型单调栈解法暴力解法
时间复杂度O(n)O(n²)
空间复杂度O(n)O(1)

说明：

  • 单调栈解法：每个元素最多入栈出栈一次，总时间复杂度为 O(n)，栈空间最大为 O(n)
  • 暴力解法：对每个元素遍历其右边所有元素，时间复杂度为 O(n²)，只需常数额外空间