Shop Leetcode 솔루션의 특별 할인으로 최종 가격  


난이도 쉽게
알고리즘 배열 코딩 Dream11 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions

Shop Leetcode 솔루션의 특별 할인이 적용된 최종 가격 문제는 귀하에게 정렬 가격. 각 제품에 대해 특별 할인을 받는다는 특별한 조건이 있습니다. 주어진 배열의 j 번째 인덱스에서 동일한 양의 요소를 할인받습니다. 주어진 배열이 학비는. 따라서 j> = i 및 가격 [j] <= prices [i]와 같은 최소 지수 인 경우 가격 [i]에 대해 가격 [j] 할인을받습니다. 그러나 솔루션을 진행하기 전에 몇 가지 예를 살펴 보겠습니다.

Shop Leetcode 솔루션의 특별 할인으로 최종 가격

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

설명 : 오른쪽에서 자신보다 작거나 같은 첫 번째 요소는 4입니다. 따라서 4에서 8를 뺍니다. 마찬가지로 나머지 요소 각각에 대해 동일한 연산을 수행합니다.

Shop Leetcode 솔루션의 특별 할인으로 최종 가격에 접근  

Shop Leetcode 솔루션에서 특별 할인이 적용되는 최종 가격 문제는 간단합니다. 그것은 매우 일반적이고 표준적인 문제에 대한 약간의 수정이라는 것을 관찰 할 수 있기 때문입니다. 문제는 스택 또는 대기열을 사용하여 해결되는 다음으로 작은 요소를 약간 수정하는 것입니다. 따라서이 문제에서도 스택을 사용하여 현재 요소보다 작거나 같은 다음 요소를 찾습니다.

참조
두 개의 정렬 된 목록 병합 Leetcode

따라서 문제를 해결하기 위해 스택을 만듭니다. 그리고 인덱스를 스택에 넣습니다. 처음에는 0이 스택으로 푸시됩니다. 이제 배열의 요소를 순회합니다. 현재 요소가 s.top () 인덱스에있는 요소보다 작거나 같은지 확인합니다. 현재 요소가 이전 조건을 충족하면 요소를 팝하고 해당 인덱스의 값을 현재 값만큼 줄입니다. 이제 현재 인덱스를 푸시합니다. 이렇게하면 다음 더 작거나 같은 요소를 찾습니다.

Shop 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

복잡성 분석  

시간 복잡성

의 위에), 입력의 모든 요소를 ​​탐색하기 때문입니다.

공간 복잡성

의 위에),  추가 공간을 사용하는 스택을 사용합니다.

1