एक शिप लेटकोड समाधानमा विशेष छुटको साथ अन्तिम मूल्यहरू


कठिनाई तह सजिलो
एरे Dream11

शिप लेटकोड समाधानमा विशेष छुटको साथ समस्याको अन्तिम मूल्यहरू बताउँछ कि तपाईंलाई एक दिइन्छ array मूल्यहरु को। त्यहाँ एक विशेष अवस्था छ कि भन्छ कि तपाईं प्रत्येक उत्पादन को लागी एक विशेष छुट छ। तपाइँले एरेमा jth अनुक्रमणिकामा एलिमेन्टको बराबर रकमको छुट पाउनुहुन्छ। मानौं कि दिइएको एर्रे छ मूल्य। त्यसोभए तपाईले मूल्यहरूको छुट पाउनुहुन्छ [j] मूल्यहरूको लागि [i] यदि j न्यूनतम अनुक्रमणिका जस्तो कि j> = i र मूल्यहरू [j] <= मूल्यहरू [i]। तर समाधान अगाडि जानु अघि हामी केही उदाहरणहरू हेरौं।

एक शिप लेटकोड समाधानमा विशेष छुटको साथ अन्तिम मूल्यहरू

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

स्पष्टीकरण: पहिलो तत्वको लागि दायाँ जुन आफै भन्दा कम वा बराबर हो So हो। त्यसैले हामी from बाट sub घटाउँछौं। त्यस्तै गरी, हामी बाँकी रहेका प्रत्येक तत्वका लागि समान कार्य गर्दछौं।

शिप लेटकोड समाधानमा विशेष छुटको साथ अन्तिम मूल्यहरूको लागि दृष्टिकोण

शिप लेटकोड समाधानमा विशेष छुटको साथ समस्याको अन्तिम मूल्यहरू सरल छ। किनभने यदि कसैले यो अवलोकन गर्न सक्दछ कि यो धेरै सामान्य र मानक समस्यामा हल्का परिमार्जन हो। समस्या अर्को सानो तत्वको एक सानो परिमार्जन हो जुन स्ट्याक वा लाम प्रयोग गरेर समाधान गरिन्छ। त्यसो भए यस समस्यामा पनि हामी स्ट्याकको प्रयोग गरी अर्को सानो वा बराबर तत्त्वलाई वर्तमान तत्वमा फेला पार्न सक्नेछौं।

त्यसैले समस्या समाधान गर्न, हामी एउटा स्ट्याक सिर्जना गर्दछौं। र हामी स्ट्याकमा सूचकांकहरू धक्का दिन्छौं। सुरुमा, ० स्ट्याकमा धक्का दिइन्छ। अब हामी एर्रेमा एलिमेन्टहरू पार गर्छौं। हामी जाँच गर्छौं कि वर्तमान तत्व 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),  हामी एउटा स्ट्याक प्रयोग गर्छौं जसले थप ठाउँ प्रयोग गर्‍यो।