وروستي قیمتونه په پلورنځي لیټکوډ حل کې د ځانګړي تخفیف سره


مشکل کچه په اسانۍ سره
پیشه Dream11

ستونزه حتمي نرخونه په هټۍ لیټکوډ حل کې د ځانګړي تخفیف سره راغلي چې تاسو ته ورکړل شوي سور د قیمتونو. یو ځانګړی حالت شتون لري چې وایي چې تاسو د هر محصول لپاره ځانګړي تخفیف ترلاسه کوئ. تاسو په ورکړل شوي صف کې د jth شاخص کې د یو عنصر مساوي مقدار تخفیف ترلاسه کوئ. راځئ چې ووایو چې ورکړل شوی صف دی نرخونه. نو تاسو د نرخونو لپاره تخفیف [j] ترلاسه کوئ [i] که j لږترلږه شاخص لکه j> = i او قیمتونه [j] <= قیمتونه [i]. مګر مخکې لدې چې حل سره مخ شئ ، راځئ چې یو څو مثالونه وګورو.

وروستي قیمتونه په پلورنځي لیټکوډ حل کې د ځانګړي تخفیف سره

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

توضیحي: د لومړي عنصر لپاره په ښي اړخ کې چې د ځان څخه لږ یا مساوي وي 4 نو موږ له 4 څخه 8 تخفیف کوو. ورته ، موږ د پاتې عناصرو لپاره ورته عملیات ترسره کوو.

په هټۍ لیټکوډ حل کې د ځانګړي تخفیف سره د وروستي قیمتونو لپاره لاره

ستونزه په هټۍ لیټکوډ حل کې د ځانګړي تخفیف سره وروستي نرخونه ساده دي. ځکه چې که یو څوک لیدلی شي چې دا د خورا عام او معیاري ستونزې په پرتله یو څه ترمیم دی. ستونزه د راتلونکي کوچني عنصر لږ بدلون دی چې د سټ یا قطار په کارولو سره حل کیږي. نو ، پدې ستونزه کې به ، موږ به اوسني عنصر ته راتلونکي کوچني یا مساوي عنصر موندلو لپاره یوه کڅوړه وکاروو.

نو د ستونزې حل کولو لپاره ، موږ یوه خونه جوړه کړه. او موږ شاخصونه په زېرمو فشار ورکوو. په پیل کې ، 0 ټیک ته فشار ورکول کیږي. اوس موږ په صف کې د عناصرو څخه تیریږو. موږ ګورو چې اوسنی عنصر کوچني دی یا د هغه عنصر سره برابر چې د s.top () شاخص کې ژوند کوي. که چیرې اوسنی عنصر پخوانی حالت پوره کړي نو بیا موږ عنصر پاپ کوو او د اوسني ارزښت په واسطه په دې شاخص کې ارزښت کمو. اوس مهال شاخص فشار کړئ. پدې توګه موږ راتلونکی کوچنی یا مساوي عنصر ومومو.

د هټۍ لیټکوډ حل کې د ځانګړي تخفیف سره د وروستي قیمتونو لپاره کوډ

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

جاوا کوډ

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

د پیچلتیا تحلیل

د وخت پیچلتیا

O (N) ، ځکه چې موږ د آخذې ټول عناصر تیروو.

د ځای پیچلتیا

O (N) ،  موږ یوه بسته وکاروو چې اضافي ځای وکاروي.