💰 商品折扣后的最终价格

📝 题目描述

​ 给定一个数组prices，其中prices[i]是商店里第i件商品的价格。现商店里正在进行促销活动，如果你要买第i件商品，那么你就可以得到与prices[j]相等的折扣，其中j是满足j > i && prices[j] <= prices[i]的最小下标，如果没有满足条件的j，则商品没有任何折扣。商品最终的价格等于原价格减去折扣。

​ 请你返回一个数组，数组中第i个元素是折扣后你购买商品i最终需要支付的价格。

🚀 示例

🖊️ 题解

模拟

​ 一个最简单的解题做法就是根据题意对整个过程进行模拟：正向遍历数组中的每个元素prices[i]，在每一轮遍历中，循环对比i之后的元素，如果发现后续元素小于等于prices[i]，则确定当前prices[i]的折扣，并结束对比、进入下一轮遍历，如果后续没有元素小于等于prices[i]，则折扣为0。

public class Solution {
    public int[] finalPrices(int[] prices) {
        int[] finalPrices = new int[prices.length];
        for (int i = 0; i < prices.length; i++) {
            int discount = 0;
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] <= prices[i]) {
                    discount = prices[j];
                    break;
                }
            }
            finalPrices[i] = prices[i] - discount;
        }
        return finalPrices;
    }
}

单调栈

​ 对于prices数组中的每个元素，它的折扣计算只关心其后续的元素，因此我们可以采用反向遍历。这样一来，当我们处理prices[i]元素时，它后续的元素就已经被处理过了。

​ 因此，该题解法的关键在于：在反向遍历过程中，应维护一种什么样的数据结构，能够更高效地计算prices中每个元素右边第一个更小（或等于）的值。答案是单调栈，每一轮遍历中，维护一个从栈底到栈顶单调递增的单调栈，具体步骤如下。

1. 创建一个初始为空的辅助栈。
2. 反向遍历prices数组。在每一轮遍历中，需沿栈顶至栈底方向，在栈中找到第一个小于等于当前元素prices[i]的元素，并将其作为折扣，同时将prices[i]压入栈中。在查询过程中，若栈顶元素不符合条件，则直接将其从栈中弹出，这是因为对于prices[i]左边的元素来说，大于prices[i]的右边元素不可能会被当作折扣。需要注意的是，在每次遍历过程中，可能会存在边界问题，即栈为空，此时则说明prices[i]后没有小于等于它的元素，折扣应为0。

public class Solution {
    public int[] finalPrices(int[] prices) {
        int[] finalPrices = new int[prices.length];
        Deque<Integer> monotonicStack = new ArrayDeque<>();
        for (int i = prices.length - 1; i >= 0; i--) {
            while (!monotonicStack.isEmpty() && monotonicStack.peek() > prices[i]){
                monotonicStack.pop();
            }
            int discount = monotonicStack.isEmpty() ? 0 : monotonicStack.peek();
            monotonicStack.push(prices[i]);
            finalPrices[i] = prices[i] - discount;
        }
        return finalPrices;
    }
}

💭 复杂度分析

​ 基于模拟的解决方案的复杂度分析如下。

• 时间复杂度：$O(n^2)$，其中$n$为商品价格数组的长度。
• 空间复杂度：$O(1)$ ，返回值不计入空间复杂度。

​ 基于单调栈的解决方案的复杂度分析如下。

• 时间复杂度：$O(n)$，其中$n$为商品价格数组的长度。
• 空间复杂度：$O(n)$ 。