商店Leetcode解决方案中的最终价格具有特别折扣  


难度级别 易得奖学金
算法 排列 编码 Dream11 访谈 面试准备 力码 力码解决方案

商店Leetcode解决方案中的带有特殊折扣的最终价格问题指出您得到了 排列 价格。 有一个特殊条件表明您可以为每种产品享受特殊折扣。 您可以在给定数组的第j个索引处获得等量元素的折扣。 假设给定的数组是 价格。 因此,如果j是最小索引,使得j> = i且prices [j] <= prices [i],则可以得到prices [i]的prices [j]折扣。 但是在继续解决方案之前,让我们看一些示例。

商店Leetcode解决方案中的最终价格具有特别折扣Pin

[8,4,6,2,3]
[4,2,4,2,3]

说明:对于右边第一个小于或等于其自身的元素为4。因此,我们从4中减去8。类似地,我们对其余每个元素执行相同的操作。

在商店Leetcode解决方案中享受特殊折扣的最终价格的方法  

在商店Leetcode解决方案中具有特殊折扣的最终价格问题很简单。 因为如果可以观察到,它是对一个非常常见且标准的问题的轻微修改。 问题是对使用堆栈或队列解决的下一个较小元素的轻微修改。 因此,同样在此问题中,我们将使用堆栈来查找当前元素的下一个较小或相等的元素。

参见
合并两个排序的列表Leetcode

因此,为了解决该问题,我们创建了一个堆栈。 然后我们将索引推入堆栈。 最初,0被压入堆栈。 现在我们遍历数组中的元素。 我们检查当前元素是否小于或等于驻留在s.top()索引上的元素。 如果当前元素满足先前条件,则我们弹出该元素,并以当前值减少该索引处的值。 现在推送当前索引。 这样,我们找到下一个较小或相等的元素。

商店Leetcode解决方案中具有特别折扣的最终价格代码  

C ++代码

#include <bits/stdc++.h>
using namespace std;

vector<int> finalPrices(vector<int>& prices) {
    stack<int> s;
    s.push(0);
    for(int i=1;i<prices.size();i++){
        while(!s.empty() && prices[s.top()] >= prices[i])prices[s.top()] -= prices[i], s.pop();
        s.push(i);
    }
    return prices;
}

int main() {
    vector<int> prices = {8,4,6,2,3};
    vector<int> output = finalPrices(prices);
    for(int i=0;i<output.size();i++)
        cout<<output[i]<<" ";
}
4 2 4 2 3

Java代码

import java.util.*;
import java.io.*;

class Main {
    public static int[] finalPrices(int[] prices) {
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < prices.length; i++) {
            while (!s.isEmpty() && prices[s.peek()] >= prices[i])
                prices[s.pop()] -= prices[i];
            s.push(i);
        }
        return prices;
    }

    public static void main(String[] args) {
        int[] prices = {8,4,6,2,3};
        int[] output = finalPrices(prices);
        for(int i=0;i<output.length;i++)
            System.out.print(output[i]+" ");
    }
}
4 2 4 2 3

复杂度分析  

时间复杂度

上), 因为我们遍历了输入的所有元素。

空间复杂度

上),  我们使用的堆栈占用了额外的空间。

1