Հատուկ զեղչով վերջնական գներ խանութի Leetcode լուծույթում


Դժվարության մակարդակ Հեշտ
Դասավորություն Dream11

Խնդիրը Վերջնական գները հատուկ զեղչով խանութում Leetcode Solution- ում նշվում է, որ ձեզ տրվում է դասավորություն գների Կա հատուկ պայման, որը ասում է, որ յուրաքանչյուր ապրանքի համար ստանում եք հատուկ զեղչ: Դուք ստանում եք տրված զանգվածի զեղչ համարժեք քանակի տարրի jth ինդեքսում: Ասենք, որ տրված զանգվածն է գները, Այսպիսով, դուք գների [j] զեղչ եք ստանում գների համար [i], եթե j նվազագույն ցուցանիշն այնպիսին է, որ j> = i և գները [j] <= գներ [i]: Բայց նախքան լուծումը սկսելը, տեսնենք մի քանի օրինակ:

Հատուկ զեղչով վերջնական գներ խանութի Leetcode լուծույթում

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

Բացատրություն. Աջ կողմում առաջին տարրի համար, որը իրենից պակաս է կամ հավասար է 4-ը. Այսպիսով, 4-ը հանում ենք 8-ից: Նմանապես, մենք մնացած տարրերից յուրաքանչյուրի համար կատարում ենք նույն գործողությունը:

Մոտեցում վերջնական գներին հատուկ զեղչով խանութի 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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք անցնում ենք մուտքի բոլոր տարրերը:

Տիեզերական բարդություն

ՎՐԱ),  մենք օգտագործում ենք մի դեղ, որն օգտագործում է լրացուցիչ տարածք: