शॉप लीटकोड सोल्यूशनमध्ये विशेष सवलतीसह अंतिम किंमती


अडचण पातळी सोपे
अरे ड्रीमएक्सएनएक्सएक्स

शॉप लीटकोड सोल्यूशनमध्ये स्पेशल डिस्काऊंटसह समस्या अंतिम किंमतींमध्ये असे म्हटले गेले आहे की आपल्याला अॅरे किंमती. अशी एक विशेष अट आहे जी सांगते की आपल्याला प्रत्येक उत्पादनांसाठी विशेष सवलत मिळते. दिलेल्या अ‍ॅरेमध्ये आपल्याला जेथ निर्देशांकात घटकाच्या समकक्ष रकमेची सूट मिळेल. समजा, दिलेला अ‍ॅरे आहे दर. म्हणून आपल्याला किंमतींसाठी [j] किंमतीची सूट मिळेल [i] जर j किमान अनुक्रमणिका जसे की जे> = i आणि किंमती [j] <= किंमती [i]. पण सोल्यूशन पुढे जाण्यापूर्वी काही उदाहरणे पाहू.

शॉप लीटकोड सोल्यूशनमध्ये विशेष सवलतीसह अंतिम किंमती

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

स्पष्टीकरणः उजवीकडील पहिल्या घटकासाठी स्वतःपेक्षा त्यापेक्षा कमी किंवा त्यासारखे 4 आहे. तर आपण 4 वरून 8 वजा करा. त्याचप्रमाणे, उर्वरित प्रत्येक घटकासाठी आम्ही समान ऑपरेशन करतो.

शॉप लीटकोड सोल्यूशनमध्ये विशेष सवलतीसह अंतिम किंमतींसाठी दृष्टिकोन

शॉप लीटकोड सोल्यूशनमध्ये विशेष सवलतीसह समस्या अंतिम किंमती सोप्या आहेत. कारण एखादी व्यक्ती अगदी सामान्य आणि प्रमाणित समस्येवर किंचित बदल केली आहे हे लक्षात घेतल्यास. अडचण पुढील लहान घटकाची थोडीशी सुधारणा आहे जी स्टॅक किंवा रांगेद्वारे सोडविली जाते. तर, या समस्येमध्ये देखील आम्ही विद्यमान घटकाला पुढील लहान किंवा समान घटक शोधण्यासाठी स्टॅक वापरू.

तर समस्येचे निराकरण करण्यासाठी आम्ही एक स्टॅक तयार करतो. आणि आम्ही निर्देशांक स्टॅकवर ढकलतो. सुरुवातीला, 0 स्टॅकवर ढकलले जाते. आता आपण अ‍ॅरे मधील घटकांकडे जाऊ. एस.टी.पी. () निर्देशांकावरील घटकांच्या तुलनेत सध्याचा घटक लहान आहे की नाही याची तपासणी करतो. जर विद्यमान घटक मागील अटीस संतुष्ट करत असेल तर आपण घटक पॉप करतो आणि त्या निर्देशांकातील मूल्य वर्तमान मूल्याद्वारे कमी करतो. आता चालू निर्देशांक ढकलणे. अशा प्रकारे आपल्याला पुढील लहान किंवा समान घटक सापडतील.

शॉप लीटकोड सोल्यूशनमध्ये विशेष सवलतीसह अंतिम किंमतींसाठी कोड

सी ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), आम्ही इनपुटमधील सर्व घटकांना मागे टाकत आहोत.

स्पेस कॉम्प्लेक्सिटी

ओ (एन),  आम्ही अतिरिक्त जागा वापरणारे एक स्टॅक वापरतो.