షాప్ లీట్‌కోడ్ సొల్యూషన్‌లో ప్రత్యేక తగ్గింపుతో తుది ధరలు  


కఠినత స్థాయి సులువు
అల్గోరిథంలు అర్రే కోడింగ్ Dream11 ఇంటర్వ్యూ ఇంటర్వ్యూ ప్రిపరేషన్ లీట్‌కోడ్ LeetCodeSolutions

షాప్ లీట్‌కోడ్ సొల్యూషన్‌లో ప్రత్యేక డిస్కౌంట్‌తో సమస్య తుది ధరలు మీకు ఇవ్వబడ్డాయి అమరిక ధరలు. ప్రతి ఉత్పత్తికి మీకు ప్రత్యేక తగ్గింపు లభిస్తుందని చెప్పే ప్రత్యేక షరతు ఉంది. మీరు ఇచ్చిన శ్రేణిలో jth సూచిక వద్ద ఒక మూలకం యొక్క సమానమైన మొత్తంలో తగ్గింపును పొందుతారు. ఇచ్చిన శ్రేణి అని చెప్పండి ధరలు. కాబట్టి మీరు j> = i మరియు ధరలు [j] <= ధరలు [i] వంటి కనీస సూచిక అయితే మీకు ధరల తగ్గింపు [j] లభిస్తుంది. కానీ పరిష్కారంతో ముందుకు వెళ్ళే ముందు, కొన్ని ఉదాహరణలు చూద్దాం.

షాప్ లీట్‌కోడ్ సొల్యూషన్‌లో ప్రత్యేక తగ్గింపుతో తుది ధరలుపిన్

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

వివరణ: కుడి వైపున ఉన్న మొదటి మూలకం దాని కంటే తక్కువ లేదా సమానంగా ఉంటుంది. కాబట్టి మనం 4 నుండి 4 ను తీసివేస్తాము. అదేవిధంగా, మిగిలిన ప్రతి మూలకానికి ఒకే ఆపరేషన్ చేస్తాము.

షాప్ లీట్‌కోడ్ సొల్యూషన్‌లో ప్రత్యేక డిస్కౌంట్‌తో తుది ధరల విధానం  

షాప్ లీట్‌కోడ్ సొల్యూషన్‌లో ప్రత్యేక డిస్కౌంట్‌తో తుది ధరలు సమస్య చాలా సులభం. ఎందుకంటే ఇది చాలా సాధారణమైన మరియు ప్రామాణికమైన సమస్యపై స్వల్ప మార్పు అని గమనించగలిగితే. సమస్య తదుపరి చిన్న మూలకం యొక్క స్వల్ప మార్పు, ఇది స్టాక్ లేదా క్యూ ఉపయోగించి పరిష్కరించబడుతుంది. కాబట్టి, ఈ సమస్యలో కూడా, ప్రస్తుత మూలకానికి తదుపరి చిన్న లేదా సమానమైన మూలకాన్ని కనుగొనడానికి మేము స్టాక్‌ను ఉపయోగిస్తాము.

ఇది కూడ చూడు
రెండు క్రమబద్ధీకరించిన జాబితాల లీట్‌కోడ్‌ను విలీనం చేయండి

కాబట్టి సమస్యను పరిష్కరించడానికి, మేము ఒక స్టాక్‌ను సృష్టిస్తాము. మరియు మేము సూచికలను స్టాక్‌కు నెట్టివేస్తాము. ప్రారంభంలో, 0 స్టాక్‌కు నెట్టబడుతుంది. ఇప్పుడు మనం శ్రేణిలోని మూలకాలపై ప్రయాణిస్తాము. ప్రస్తుత మూలకం s.top () సూచికలో నివసించే మూలకానికి చిన్నదా లేదా సమానంగా ఉందా అని మేము తనిఖీ చేస్తాము. ప్రస్తుత మూలకం మునుపటి పరిస్థితిని సంతృప్తిపరిస్తే, అప్పుడు మేము మూలకాన్ని పాప్ చేసి, ప్రస్తుత విలువ ద్వారా ఆ సూచిక వద్ద విలువను తగ్గిస్తాము. ఇప్పుడు ప్రస్తుత సూచికను నెట్టండి. ఈ విధంగా మేము తదుపరి చిన్న లేదా సమాన మూలకాన్ని కనుగొంటాము.

షాప్ లీట్‌కోడ్ సొల్యూషన్‌లో ప్రత్యేక తగ్గింపుతో తుది ధరల కోసం కోడ్  

సి ++ కోడ్

#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

సంక్లిష్టత విశ్లేషణ  

సమయం సంక్లిష్టత

పై), మేము ఇన్పుట్ యొక్క అన్ని అంశాలను దాటుతున్నందున.

అంతరిక్ష సంక్లిష్టత

పై),  మేము అదనపు స్థలాన్ని ఉపయోగించిన స్టాక్‌ను ఉపయోగిస్తాము.

1