Mağazada Leetcode həllində xüsusi endirimlə son qiymətlər

Çətinlik səviyyəsi Asan
alqoritmlər Geyim kodlaşdırma Dream11 müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 32

Problem Bir Mağazada Xüsusi Endirimlə Son Qiymətlər Leetcode Solution sizə verildiyini bildirir array qiymətlər. Məhsulların hər biri üçün xüsusi endirim aldığınızı söyləyən xüsusi bir şərt var. Verilən massivdə jth indeksində bir elementə bərabər miqdarda endirim əldə edirsiniz. Verilən massivin belə olduğunu deyək qiymətləri. Beləliklə, qiymətlər üçün endirim əldə edirsiniz [j] qiymətlər üçün [i] əgər j minimum indeks belə j> = i və qiymətlər [j] <= qiymətlər [i] olsun. Ancaq həlli davam etməzdən əvvəl bir neçə nümunəyə baxaq.

Mağazada Leetcode həllində xüsusi endirimlə son qiymətlərPin

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

İzahat: Sağdakı özündən az və ya ona bərabər olan ilk element 4-dür. Buna görə 4-dən 8-ü çıxardırıq. Eynilə, qalan elementlərin hər biri üçün eyni əməliyyatı yerinə yetiririk.

Mağazada Leetcode həllində xüsusi endirimlə son qiymətlərə yanaşma

Mağaza Leetcode Çözümündə Xüsusi Endirimlə Son Qiymətlər sadədir. Çünki çox ümumi və standart bir problem üzərində yüngül bir dəyişiklik olduğunu müşahidə etmək olarsa. Problem bir yığın və ya növbə istifadə edərək həll edilən növbəti kiçik elementin cüzi bir dəyişiklikidir. Beləliklə, bu problemdə, cari elementə növbəti kiçik və ya bərabər elementi tapmaq üçün bir yığın istifadə edəcəyik.

Yəni problemi həll etmək üçün bir yığın yaradırıq. Və indeksləri yığına itələyirik. Başlanğıcda, 0 yığına sıxışdırılır. İndi serialdakı elementlərin üstündən keçirik. Cari elementin s.top () indeksində yerləşən elementə nisbətən kiçik və ya bərabər olduğunu yoxlayırıq. Cari element əvvəlki şərti təmin edirsə, elementi açırıq və indeksdəki dəyəri cari dəyərlə azaldırıq. İndi mövcud göstəricini itələyin. Bu şəkildə növbəti kiçik və ya bərabər elementi tapırıq.

Bir Mağazada Xüsusi Endirimlə Son Qiymətlər Kodu Leetcode Həlli

C ++ kodu

#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

Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki girişin bütün elementlərini keçirik.

Kosmik Mürəkkəblik

O (N),  əlavə yer istifadə edən bir yığından istifadə edirik.

Şərh yaz

Translate »
1