מחירים סופיים עם הנחה מיוחדת בפתרון Leetcode Shop


רמת קושי קַל
מערך Dream11

הבעיה המחירים הסופיים עם הנחה מיוחדת בפתרון Leetcode של חנות קובעת שמקבלים לך מערך של מחירים. יש תנאי מיוחד שאומר שאתה מקבל הנחה מיוחדת לכל אחד מהמוצרים. אתה מקבל הנחה של סכום שווה ערך של אלמנט באינדקס jth במערך הנתון. בואו נגיד שהמערך הנתון הוא מחירים. אז אתה מקבל הנחה במחירים [j] למחירים [i] אם j המדד המינימלי כך ש j> = i והמחירים [j] <= מחירים [i]. אך לפני שנמשיך עם הפתרון, בואו נראה כמה דוגמאות.

מחירים סופיים עם הנחה מיוחדת בפתרון Leetcode Shop

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

הסבר: עבור האלמנט הראשון בצד ימין שהוא קטן או שווה לעצמו הוא 4. אז אנו מפחיתים 4 מ- 8. באופן דומה, אנו מבצעים אותה פעולה עבור כל אחד מהאלמנטים הנותרים.

גישה למחירים סופיים עם הנחה מיוחדת בפתרון Leetcode Shop

הבעיה המחירים הסופיים עם הנחה מיוחדת בפתרון Leetcode של חנות היא פשוטה. כי אם אפשר להתבונן שמדובר בשינוי קל בגלל בעיה נפוצה וסטנדרטית מאוד. הבעיה היא שינוי קל של האלמנט הבא הקטן יותר שנפתר באמצעות מחסנית או תור. לכן, גם בבעיה זו נשתמש בערימה כדי למצוא את האלמנט הקטן או השווה הבא לאלמנט הנוכחי.

אז כדי לפתור את הבעיה, אנו יוצרים ערימה. ואנחנו דוחפים מדדים אל הערימה. בתחילה, 0 נדחק אל הערימה. כעת אנו חוצים את האלמנטים במערך. אנו בודקים אם האלמנט הנוכחי קטן או שווה לאלמנט השוכן באינדקס s.top (). אם האלמנט הנוכחי עומד בתנאי הקודם, אנו מקפצים את האלמנט ומפחיתים את הערך באינדקס בערך הנוכחי. כעת לחץ על המדד הנוכחי. בדרך זו אנו מוצאים את האלמנט הקטן או השווה הבא.

קוד למחירים סופיים עם הנחה מיוחדת בפתרון Leetcode של חנות

קוד 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)  אנו משתמשים בערימה ששימשה מקום נוסף.