LeetCode 1475: Final Prices With a Special Discount in a Shop

Explanation:

• We can solve this problem using a stack data structure to keep track of the indices of prices where we have not found a greater or equal price yet.
• We iterate through each price in the array. If the current price is less than the price at the top of the stack, we calculate the discount and update the final price for the top of the stack.
• If the current price is greater than or equal to the price at the top of the stack, we continue to pop items from the stack and update their final prices until we find a price greater than the current price.
• Finally, we return the array containing the final prices. :

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