29-Final-Prices-With-Discount.md

Final Prices With Discount

Problem Link

https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/

---

Pattern

• Stack
• Monotonic Stack

---

Approach

Use a monotonic stack to find the next smaller or equal price for each item.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = Arrays.copyOf(prices, n);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                ans[stack.pop()] -= prices[i];
            }
            stack.push(i);
        }
        return ans;
    }
}