Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

简介

本文主要介绍了使用单调栈实现leetcode145道题目的算法思路以及Java、C++两种语言的代码实现。

题目描述：给定一个数组prices表示商品每一天的价格，并且在购买这个商品时，会给出一个最大的折扣价格，那么在每天商品的价格和折扣价格之间取一个较低的价钱，输出折扣后的最终价格。

算法思路

使用单调栈实现该题目的算法步骤如下：

• 构建一个单调递减栈；
• 遍历原始数组，如果当前元素小于等于栈顶元素，则入栈；
• 如果当前元素大于栈顶元素，则弹出栈顶元素，计算折扣后的价格，并将结果保存到数组中；
• 遍历完整个数组后，单调栈中剩余的元素均为没有折扣的商品，将它们的价格保存到数组中即可。

Java代码实现示例

public int[] finalPrices(int[] prices) {
    int n = prices.length;
    int[] res = new int[n];
    Arrays.fill(res, -1); //设置默认折扣为 -1

    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && prices[i] <= prices[stack.peek()]) {
            int j = stack.pop();
            res[j] = prices[j] - prices[i];
        }
        stack.push(i);
    }

    for (int i = 0; i < n; i++) {
        if (res[i] == -1) {
            res[i] = prices[i];
        }
    }

    return res;
}

C++代码实现示例

vector<int> finalPrices(vector<int>& prices) {
    int n = prices.size();
    vector<int> res(n, -1);

    stack<int> stack;
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && prices[i] <= prices[stack.top()]) {
            int j = stack.top();
            stack.pop();
            res[j] = prices[j] - prices[i];
        }
        stack.push(i);
    }

    for (int i = 0; i < n; i++) {
        if (res[i] == -1) {
            res[i] = prices[i];
        }
    }

    return res;
}

示例说明

• 示例1:

输入: prices = [8,4,6,2,3]

输出: [4,2,4,2,3]

• 示例2:

输入: prices = [1,2,3,4,5]

输出: [1,2,3,4,5]

以上是使用单调栈实现leetcode145商品折扣后最终价格题目的完整攻略，供大家参考。