💬 Discord
Sign In
NeetCode #348LC-1475EasyStack
← Back to All Problems

#348 · #1475 · Final Prices With a Special Discount in a Shop(商品折扣后的最终价格)

📌 Problem Statement & Constraints

You are given an array prices where prices[i] is the price of the i-th item. If there is an index j > i with prices[j] <= prices[i], you receive a discount equal to prices[j]; otherwise no discount. Return the final prices. Constraints: 1 <= prices.length <= 500, 1 <= prices[i] <= 1000.

💡 Core Algorithmic Approaches

  1. This is "next smaller or equal element", the mirror of Daily Temperatures.
  2. A monotonically increasing stack of indices holds items still waiting for a discount.
  3. When a new price arrives, pop every index whose price is at least the new price and apply the discount.
  4. Items left on the stack get no discount.

💻 Benchmark Python3 Implementation

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        res = prices[:]
        st = []                            # indices waiting for a discount
        for i, p in enumerate(prices):
            while st and prices[st[-1]] >= p:
                j = st.pop()
                res[j] = prices[j] - p     # apply the discount
            st.append(i)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each index is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Using > instead of >=: a discount applies when the later price is less than or equal to the current price.
  • Mutating prices in place and then reading it: the comparison must use the original prices, so keep them intact and write into a copy.
  • Applying the discount to the wrong index: the popped index j receives it, not i.
  • Using a nested loop: O(n^2), though acceptable at n <= 500.