Крайни цени със специална отстъпка в решение за магазин Leetcode


Ниво на трудност Лесно
Array Dream11

Проблемът Крайни цени със специална отстъпка в магазин Leetcode Solution гласи, че ви се дава масив на цените. Има специално условие, което гласи, че получавате специална отстъпка за всеки от продуктите. Получавате отстъпка от еквивалентно количество от елемент с j-ти индекс в дадения масив. Да кажем, че даденият масив е цени. Така получавате отстъпка от цени [j] за цени [i], ако j минималният индекс, такъв че j> = i и цени [j] <= цени [i]. Но преди да продължим с решението, нека видим няколко примера.

Крайни цени със специална отстъпка в решение за магазин Leetcode

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

Обяснение: За първия елемент вдясно, който е по-малък или равен на себе си, е 4. Така че изваждаме 4 от 8. По същия начин извършваме една и съща операция за всеки от останалите елементи.

Подход за крайни цени със специална отстъпка в решение за магазин Leetcode

Проблемът Крайни цени със специална отстъпка в магазина Leetcode Solution е прост. Защото, ако човек може да забележи, че това е леко изменение върху много често срещан и стандартен проблем. Проблемът е малка модификация на следващия по-малък елемент, който се решава с помощта на стек или опашка. И така, и в този проблем ще използваме стека, за да намерим следващия по-малък или равен на текущия елемент елемент.

Така че, за да разрешим проблема, ние създаваме стек. И ние натискаме индекси към стека. Първоначално 0 се избутва в стека. Сега преминаваме през елементите в масива. Проверяваме дали текущият елемент е по-малък или равен на елемента, който се намира в индекса s.top (). Ако текущият елемент отговаря на предишното условие, тогава ние изваждаме елемента и намаляваме стойността при този индекс с текущата стойност. Сега натиснете текущия индекс. По този начин намираме следващия по-малък или равен елемент.

Код за крайни цени със специална отстъпка в магазин Leetcode Solution

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

Java код

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

Анализ на сложността

Сложност във времето

НА), тъй като обхождаме всички елементи на входа.

Сложност на пространството

НА),  ние използваме стек, който използва допълнително пространство.