શોપ લિટકોડ સોલ્યુશનમાં વિશેષ ડિસ્કાઉન્ટ સાથે અંતિમ કિંમતો


મુશ્કેલી સ્તર સરળ
અરે ડ્રીમએક્સએક્સએક્સ

દુકાન લીટકોડ સોલ્યુશનમાં વિશેષ ડિસ્કાઉન્ટ સાથેની અંતિમ કિંમતો જણાવે છે કે તમને એક આપવામાં આવે છે એરે ભાવ. ત્યાં એક વિશેષ શરત છે જે કહે છે કે તમને દરેક ઉત્પાદનો માટે વિશેષ છૂટ મળે છે. આપેલ એરેમાં jth અનુક્રમણિકા પર તમને ઘટકની સમકક્ષ રકમની છૂટ મળશે. ચાલો આપણે કહીએ કે આપેલ એરે છે ભાવ. તેથી તમને કિંમતો માટે છૂટ મળશે [j] કિંમતો [i] જો j લઘુત્તમ અનુક્રમણિકા જેમ કે j> = i અને કિંમતો [j] <= કિંમતો [i]. પરંતુ સોલ્યુશન સાથે આગળ વધતા પહેલા, આપણે થોડા ઉદાહરણો જોઈએ.

શોપ લિટકોડ સોલ્યુશનમાં વિશેષ ડિસ્કાઉન્ટ સાથે અંતિમ કિંમતો

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

સમજૂતી: જમણી બાજુના પ્રથમ તત્વ માટે કે જે પોતાને કરતા ઓછું અથવા બરાબર છે 4 છે. તેથી આપણે 4 થી 8 બાદ કરીએ છીએ. એ જ રીતે, આપણે બાકીના દરેક તત્વો માટે સમાન ક્રિયા કરીએ છીએ.

શોપ લિટકોડ સોલ્યુશનમાં વિશેષ ડિસ્કાઉન્ટ સાથે અંતિમ કિંમતો માટે અભિગમ

દુકાન લીટકોડ સોલ્યુશનમાં વિશેષ ડિસ્કાઉન્ટ સાથેની અંતિમ કિંમતો સરળ છે. કારણ કે જો કોઈ અવલોકન કરી શકે છે કે તે ખૂબ સામાન્ય અને માનક સમસ્યા પર થોડો ફેરફાર છે. સમસ્યા એ પછીના નાના તત્વોમાં થોડો ફેરફાર છે જે સ્ટેક અથવા કતારની મદદથી ઉકેલી શકાય છે. તેથી, આ સમસ્યામાં પણ, આપણે વર્તમાન તત્વની સાથે આગામી નાના અથવા સમાન તત્વ શોધવા માટે સ્ટેકનો ઉપયોગ કરીશું.

તેથી સમસ્યા હલ કરવા માટે, અમે એક સ્ટેક બનાવીએ છીએ. અને અમે સૂચકાંકોને સ્ટેક પર દબાણ કરીએ છીએ. શરૂઆતમાં, 0 ને સ્ટેક પર દબાણ કરવામાં આવે છે. હવે આપણે એરેમાં રહેલા તત્વો ઉપર પસાર કરીશું. અમે તપાસો કે વર્તમાન તત્વ એ.એસ.ટtopપ () અનુક્રમણિકા પરના તત્વની તુલનામાં નાનું અથવા બરાબર છે કે નહીં. જો વર્તમાન તત્વ પાછલી સ્થિતિને સંતોષે છે, તો અમે ઘટકને પ popપ કરીએ છીએ અને વર્તમાન સૂચકાંકમાં તે મૂલ્યને વર્તમાન મૂલ્ય દ્વારા ઘટાડીએ છીએ. હવે ચાલુ અનુક્રમણિકાને દબાણ કરો. આ રીતે આપણે આગળનું નાનું અથવા સમાન તત્વ શોધીએ છીએ.

શોપ લિટકોડ સોલ્યુશનમાં વિશેષ ડિસ્કાઉન્ટ સાથે અંતિમ કિંમતો માટેનો કોડ

સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે આપણે ઇનપુટના બધા તત્વોને વટાવીએ છીએ.

અવકાશ જટિલતા

ઓ (એન),  અમે એક સ્ટેકનો ઉપયોગ કરીએ છીએ જેમાં વધારાની જગ્યા વપરાય છે.