Leetcode # 1475. Final Prices With a Special Discount in a Shop

Problem

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

∀ i in range(prices), 
If ∃ js = [j for j in range(i + 1, len(prices)) if (j > i and prices[j] <= prices[i])] ≠∅
⇒ prices[i] -= prices[min(js)].
Otherwise, prices[i] stays as it is.

※ j > i and prices[j] <= prices[i]
 i < j and prices[i] >= prices[j] 個人認為視覺上比較容易理解

Testcases

First Try: Two Pointers

如上 testcase #12
prices[6] (7) <= prices[7] (7) <= prices[9] (1)
理應選擇 prices[7] 而非 prices[9]

Time Complexity: O(len(prices))
Space Complexity: O(len(prices))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    ans = left = curr = 0
    discount = [0]
    discount_i = [0] * len(prices)
    for right in range(len(prices)):
      if right > left and prices[right] <= prices[left]:
        discount[-1] = prices[right]
        discount.append(0)
        left = right
      discount_i[right] = len(discount) - 1
    return [(price - discount[discount_i[i]]) for i, price in enumerate(prices)]

Solution: Brute-Force

Time Complexity: O(len(prices) ** 2)
Space Complexity: O(len(prices))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    return [prices[i] - (prices[min([j for j in range(i + 1, len(prices)) if (j > i and prices[j] <= prices[i])])] if len([j for j in range(i + 1, len(prices)) if (j > i and prices[j] <= prices[i])]) else 0) for i in range(len(prices))]

或

class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    for i in range(len(prices)):
      js = [j for j in range(i + 1, len(prices)) \
          if (j > i and prices[j] <= prices[i])]
      if len(js): prices[i] -= prices[js[0]]
    return prices

Solution: Binary Search

Time Complexity: O(len(prices) ** 2)
Space Complexity: O(len(prices))
(The input and output generally do not count towards the space complexity.)

from bisect import bisect
class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    sorted_prices = \
        sorted([(price, i) \
        for i, price in enumerate(prices[1:], 1)])
  
    def get_price(e):
      return e[0]

    for i, price in enumerate(prices):
      j = bisect(sorted_prices, \
          get_price((price, i)), key=get_price)
      min_i, min_k = len(prices), len(sorted_prices)
      for k in range(j):
        if sorted_prices[k][1] <= i: continue
        if sorted_prices[k][1] < min_i:
          min_i, min_k = sorted_prices[k][1], k
      discount = sorted_prices[min_k][0] \
          if min_k != len(sorted_prices) else 0
      prices[i] -= discount
    return prices

Solution: Monotonic Stack

Time Complexity: O(len(prices))
Space Complexity: O(len(prices))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    stack = [0]
    for i, price in enumerate(prices[1:], 1):
      while stack and price <= prices[stack[-1]]: 
        prices[stack.pop()] -= price
      stack.append(i)
    return prices

Last Updated on 2024/12/18 by A1go