ਇੱਕ ਦੁਕਾਨ ਲੀਟਕੋਡ ਹੱਲ ਵਿੱਚ ਇੱਕ ਵਿਸ਼ੇਸ਼ ਛੂਟ ਦੇ ਨਾਲ ਅੰਤਮ ਭਾਅ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਰੇ ਡ੍ਰੀਮਐਕਸਯੂ.ਐੱਨ.ਐੱਮ.ਐੱਮ.ਐਕਸ

ਇੱਕ ਦੁਕਾਨ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਇੱਕ ਖ਼ਾਸ ਛੂਟ ਨਾਲ ਸਮੱਸਿਆ ਅੰਤਮ ਭਾਅ ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਇੱਕ ਐਰੇ ਕੀਮਤਾਂ ਦੀ. ਇੱਥੇ ਇੱਕ ਵਿਸ਼ੇਸ਼ ਸ਼ਰਤ ਹੈ ਜੋ ਕਹਿੰਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਹਰੇਕ ਉਤਪਾਦ ਲਈ ਵਿਸ਼ੇਸ਼ ਛੂਟ ਮਿਲਦੀ ਹੈ. ਤੁਹਾਨੂੰ ਦਿੱਤੇ ਐਰੇ ਵਿਚ jth ਇੰਡੈਕਸ 'ਤੇ ਇਕ ਐਲੀਮੈਂਟ ਦੀ ਇਕ ਬਰਾਬਰ ਮਾਤਰਾ ਦੀ ਛੂਟ ਮਿਲੇਗੀ. ਦੱਸ ਦੇਈਏ ਕਿ ਦਿੱਤੀ ਗਈ ਐਰੇ ਹੈ ਭਾਅ. ਇਸ ਲਈ ਤੁਸੀਂ ਕੀਮਤਾਂ ਲਈ ਛੂਟ ਪ੍ਰਾਪਤ ਕਰਦੇ ਹੋ [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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਇਨਪੁਟ ਦੇ ਸਾਰੇ ਤੱਤ ਪਾਰ ਕਰਦੇ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ),  ਅਸੀਂ ਇੱਕ ਸਟੈਕ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ ਜਿਸ ਵਿੱਚ ਅਤਿਰਿਕਤ ਜਗ੍ਹਾ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਜਾਂਦੀ ਹੈ.