Окончательные цены со специальной скидкой в ​​магазине Leetcode Solution


Сложный уровень Легко
массив Dream11

Проблема Окончательные цены со специальной скидкой в ​​решении Leetcode в магазине гласит, что вам предоставляется массив цен. Есть специальное условие, которое гласит, что вы получаете специальную скидку на каждый товар. Вы получаете скидку в размере эквивалентного количества элемента с j-м индексом в данном массиве. Скажем, данный массив Цены. Таким образом, вы получаете скидку на цены [j] для цен [i], если j минимальный индекс такой, что j> = i и цены [j] <= price [i]. Но прежде чем приступить к решению, давайте посмотрим на несколько примеров.

Окончательные цены со специальной скидкой в ​​магазине Leetcode Solution

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

Объяснение: Для первого элемента справа, который меньше или равен самому себе, равен 4. Итак, мы вычитаем 4 из 8. Точно так же мы выполняем ту же операцию для каждого из оставшихся элементов.

Подход к окончательной цене со специальной скидкой в ​​магазине Leetcode Solution

Проблема окончательных цен со специальной скидкой в ​​магазине 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

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

Сложность времени

НА), так как мы обходим все элементы ввода.

Космическая сложность

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