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

给你一个数组 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] <= 10^3

方法一：直接遍历

对于第 i 件商品的价格为 prices}[i]，我们需要查找到相应可能的折扣。按照题目要求，我们从第 i + 1 件商品开始依次向后遍历，直到找到第一个满足 prices}[j] \le \textit{prices}[i] 的下标 j 即可求出该物品的最终折扣价格。我们按照题目要求依次遍历即可。

[sol1-Python3]

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        ans = [0] * n
        for i, p in enumerate(prices):
            discount = 0
            for j in range(i + 1, n):
                if prices[j] <= p:
                    discount = prices[j]
                    break
            ans[i] = p - discount
        return ans

[sol1-C++]

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            int discount = 0;
            for (int j = i + 1; j < n; ++j) {
                if(prices[j] <= prices[i]){
                    discount = prices[j];
                    break;
                }
            }
            ans.emplace_back(prices[i] - discount);
        }
        return ans;
    }
};

[sol1-Java]

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

[sol1-C#]

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

[sol1-C]

int* finalPrices(int* prices, int pricesSize, int* returnSize) {
    int *ans = (int *)malloc(sizeof(int) * pricesSize);
    for (int i = 0; i < pricesSize; ++i) {
        int discount = 0;
        for (int j = i + 1; j < pricesSize; ++j) {
            if(prices[j] <= prices[i]){
                discount = prices[j];
                break;
            }
        }
        ans[i] = prices[i] - discount;
    }
    *returnSize = pricesSize;
    return ans;
}

[sol1-JavaScript]

var finalPrices = function(prices) {
    const n = prices.length;
    const ans = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        let discount = 0;
        for (let j = i + 1; j < n; ++j) {
            if(prices[j] <= prices[i]){
                discount = prices[j];
                break;
            }
        }
        ans[i] = prices[i] - discount;
    }
    return ans;
};  

[sol1-Golang]

func finalPrices(prices []int) []int {
    ans := make([]int, len(prices))
    for i, p := range prices {
        discount := 0
        for _, q := range prices[i+1:] {
            if q <= p {
                discount = q
                break
            }
        }
        ans[i] = p - discount
    }
    return ans
}

复杂度分析

• 时间复杂度：O(n ^ 2)，其中 n 为数组的长度。对于每个商品，我们需要遍历一遍数组查找符合题目要求的折扣。

• 空间复杂度：O(1)。返回值不计入空间复杂度。

方法二：单调栈

本题可以采用「单调栈 」的解法，可以参考「496. 下一个更大元素 I 的官方题解 」。使用单调栈先预处理 prices，使得查询 prices 中每个元素对应位置的右边的第一个更小的元素值时不需要再遍历 prices。解法的重点在于考虑如何更高效地计算 prices 中每个元素右边第一个更小的值。倒序遍历 prices，并用单调栈中维护当前位置右边的更小的元素列表，从栈底到栈顶的元素是单调递增的。具体每次我们移动到数组中一个新的位置 i，就将单调栈中所有大于 prices}[i] 的元素弹出单调栈，当前位置右边的第一个小于等于 prices}[i] 的元素即为栈顶元素，如果栈为空则说明当前位置右边没有更大的元素，随后我们将位置 i 的元素入栈。

当遍历第 i 个元素 prices}[i] 时：

• 如果当前栈顶的元素大于 prices}[i]，则将栈顶元素出栈，直到栈顶的元素小于等于 prices}[i]，栈顶的元素即为右边第一个小于 prices}[i] 的元素；

• 如果当前栈顶的元素小于等于 prices}[i]，此时可以知道当前栈顶元素即为 i 的右边第一个小于等于 prices}[i] 的元素，此时第 i 个物品折后的价格为 prices}[i] 与栈顶的元素的差。

• 如果当前栈中的元素为空，则此时折扣为 0，商品的价格为原价 prices}[i]；

• 将 prices}[i] 压入栈中，保证 prices}[i] 为当前栈中的最大值；

[sol2-Python3]

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        ans = [0] * n
        st = [0]
        for i in range(n - 1, -1, -1):
            p = prices[i]
            while len(st) > 1 and st[-1] > p:
                st.pop()
            ans[i] = p - st[-1]
            st.append(p)
        return ans

[sol2-C++]

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

[sol2-Java]

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

[sol2-C#]

public class Solution {
    public int[] FinalPrices(int[] prices) {
        int n = prices.Length;
        int[] ans = new int[n];
        Stack<int> stack = new Stack<int>();
        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && stack.Peek() > prices[i]) {
                stack.Pop();
            }
            ans[i] = stack.Count == 0 ? prices[i] : prices[i] - stack.Peek();
            stack.Push(prices[i]);
        }
        return ans;
    }
}

[sol2-C]

int* finalPrices(int* prices, int pricesSize, int* returnSize) {
    int *ans = (int *)malloc(sizeof(int) * pricesSize);
    int *stack = (int *)malloc(sizeof(int) * pricesSize);
    int top = 0;
    for (int i = pricesSize - 1; i >= 0; i--) {
        while (top > 0 && stack[top - 1] > prices[i]) {
            top--;
        }
        ans[i] = top == 0 ? prices[i] : prices[i] - stack[top - 1];
        stack[top++] = prices[i];
    }
    *returnSize = pricesSize;
    free(stack);
    return ans;
}

[sol2-JavaScript]

var finalPrices = function(prices) {
    const n = prices.length;
    const ans = new Array(n).fill(0);
    const stack = [];
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length && stack[stack.length - 1] > prices[i]) {
            stack.pop();
        }
        ans[i] = stack.length === 0 ? prices[i] : prices[i] - stack[stack.length - 1];
        stack.push(prices[i]);
    }
    return ans;
};  

[sol2-Golang]

func finalPrices(prices []int) []int {
    n := len(prices)
    ans := make([]int, n)
    st := []int{0}
    for i := n - 1; i >= 0; i-- {
        p := prices[i]
        for len(st) > 1 && st[len(st)-1] > p {
            st = st[:len(st)-1]
        }
        ans[i] = p - st[len(st)-1]
        st = append(st, p)
    }
    return ans
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组的长度。只需遍历一遍数组即可。

• 空间复杂度：O(n)。需要栈空间存储中间变量，需要的空间为 O(n)。