题目描述

给你一个数组 prices，其中 prices[i] 是商店里第 i 件商品的价格。商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的最小下标，如果没有满足条件的 j，你将没有任何折扣。请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

例如：prices = [8,4,6,2,3]，输出 [4,2,4,2,3]。

解释：商品 0 价格 8，右侧第一个 <= 8 的是价格 4，最终支付 8-4=4；商品 1 价格 4，右侧第一个 <= 4 的是价格 2，最终支付 4-2=2；商品 2 价格 6，右侧第一个 <= 6 的是价格 2，最终支付 6-2=4；商品 3 价格 2，右侧无 <= 2 的元素，最终支付 2；商品 4 价格 3，右侧无元素，最终支付 3。

解题思路

暴力法

对每个元素，向右侧扫描寻找第一个不大于它的元素，时间复杂度 O(n²)。

单调栈解法（O(n)）

本题是寻找右侧第一个小于等于当前元素的元素的经典问题，可以用单调递增栈解决。

核心思想：

  1. 初始化结果数组 res，默认值为 prices[i]（即无折扣时的价格）。
  2. 维护一个从栈底到栈顶递增的栈，栈中存储下标。
  3. 遍历 prices，对于当前商品 i：
    • 当栈不为空且当前价格 prices[i] <= 栈顶下标对应的价格时：
      • 说明栈顶商品找到了最近的 <= 它的价格，可以享受折扣。
      • 弹出栈顶下标 index，计算 res[index] = prices[index] - prices[i]。
    • 将当前下标 i 入栈。
  4. 遍历结束后，栈中剩余元素没有折扣，res 中保持原价即可。

为什么单调栈可以解决问题？

以 [8,4,6,2,3] 为例，模拟过程：

  • i=0（价格 8）：栈空，入栈 [0]
  • i=1（价格 4）：4 < 8，弹出 0，res[0]=8-4=4；入栈 [1]
  • i=2（价格 6）：6 > 4，不弹出；入栈 [1,2]
  • i=3（价格 2）：2 < 6，弹出 2，res[2]=6-2=4；2 < 4，弹出 1，res[1]=4-2=2；入栈 [3]
  • i=4（价格 3）：3 > 2，不弹出；入栈 [3,4]
  • 结束，栈中 [3,4] 无折扣，最终为 [4,2,4,2,3]

每个元素最多进栈一次、出栈一次，总时间复杂度 O(n)。

复杂度分析

  • 时间复杂度：O(n)，每个元素最多入栈和出栈各一次。
  • 空间复杂度：O(n)，最坏情况下栈中存储所有元素下标。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package code.J1475;

import java.util.ArrayDeque;
import java.util.Deque;

public class J1475 {
    public int[] finalPrices(int[] prices) {
        int[] res = new int[prices.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < prices.length; i++) {
            res[i] = prices[i];
            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                int index = stack.pop();
                res[index] = prices[index] - prices[i];
            }
            stack.push(i);
        }
        return res;
    }
}