1475. Final Prices With a Special Discount in a Shop (Easy) (https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/)
You are given an integer array prices where prices[i] is the price of the ith item in a shop. There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all. Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount. Constraints: 1 <= prices.length <= 500 1 <= prices[i] <= 1000
function finalPrices(prices: number[]): number[] {
const discounted: number[] = [];
const stack: number[] = [];
for (let i = 0; i < prices.length; i++) {
discounted[i] = prices[i];
// i является скидкой для тех в стеке, чья цена >= prices[i]
while (stack.length > 0 && prices[stack.at(-1)!] >= prices[i]) {
const topIdx = stack.pop()!;
discounted[topIdx] -= prices[i];
}
stack.push(i);
}
return discounted;
}
/* v2 */
function finalPrices2(prices: number[]): number[] {
const answer: number[] = [];
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
if (j > i && prices[j] <= prices[i]) {
answer.push(prices[i] - prices[j]);
break;
}
}
if (answer.length < i + 1 || answer.length === 0) {
answer.push(prices[i]);
}
}
return answer;
}
// Local check:
console.log(finalPrices([8, 4, 6, 2, 3]));
console.log(finalPrices([1, 2, 3, 4, 5]));
console.log(finalPrices([10, 1, 1, 6]));
<!-- [[leetcode/array]] [[leetcode/array/1470-shuffle-the-array]] [[leetcode/array/150-evaluate-reverse-polish-notation]] -->Example 1:
Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation:
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
For items 3 and 4 you will not receive any discount at all.
Example 2:
Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: In this case, for all items, you will not receive any discount at all.
Example 3:
Input: prices = [10,1,1,6]
Output: [9,0,1,6]