1475. Final Prices With a Special Discount in a Shop
Problem
You are given an integer array prices where prices[i] is the price of the iᵗʰ item in a shop.
There is a special discount for items in the shop. If you buy the iᵗʰ 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.
https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/
Example 1:
Input:
prices = [8,4,6,2,3]
Output:[4,2,4,2,3]
Explanation:
For item 0 withprice[0]=8you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is8 - 4 = 4.
For item 1 withprice[1]=4you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is4 - 2 = 2.
For item 2 withprice[2]=6you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is6 - 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]
Constraints:
1 <= prices.length <= 5001 <= prices[i] <= 1000
Test Cases
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:import pytest
from solution import Solution
from solution_nlogn import Solution as SolutionNlogn
from solution_n import Solution as SolutionN
from solution_n2 import Solution as SolutionN2
@pytest.mark.parametrize('prices, expected', [
([8,4,6,2,3], [4,2,4,2,3]),
([1,2,3,4,5], [1,2,3,4,5]),
([10,1,1,6], [9,0,1,6]),
])
@pytest.mark.parametrize('sol', [Solution(), SolutionNlogn(), SolutionN(), SolutionN2()])
class Test:
def test_solution(self, sol, prices, expected):
assert sol.finalPrices(prices.copy()) == expected
Thoughts
按题目限定的规模,直接暴力(brute force)就够了。对于位置 i,从 i + 1 开始找到第一个不高于 prices[i] 的价格,作为折扣减去即可。
时间复杂度 O(n²),附加的空间复杂度 O(1)。
Code
class Solution:
def finalPrices(self, prices: list[int]) -> list[int]:
n = len(prices)
for i in range(n - 1):
for j in range(i + 1, n):
if prices[j] <= prices[i]:
prices[i] -= prices[j]
break
return prices
O(n log n)
有点儿类似 1847. Closest Room,事先对 prices 排序,从小到大扫描,把不高于当前价格的商品加入到有序集合,该有序集合按商品下标保持有序。然后在该有序集合中用二分法查找当前价格的下标,找到大于其下标中的最小。
扫描排序后 prices 的过程中,所有已经处理过的就都不比当前价格高,对于重复的相等价格,可以在前边排序的时候,优先按价格,其次按下标(逆序)排序,确保可选的商品一定会被先处理。
时间复杂度 O(n log n)(虽然 Python list 的 bisect.insort 也是 O(n) 时间,但在当下规模下还是比较快的,更大规模可以用其他有序集合的实现),空间复杂度 O(n)。
不过实际提交跑就很慢,可能系数太大了。
from bisect import bisect_left, insort
class Solution:
def finalPrices(self, prices: list[int]) -> list[int]:
n = len(prices)
indices = sorted(range(n), key=lambda i: (prices[i], -i))
results = list(prices)
valid_items = []
for i in indices:
idx = bisect_left(valid_items, i + 1)
if idx < len(valid_items):
results[i] -= prices[valid_items[idx]]
insort(valid_items, i)
return results
O(n)
这种找左侧/右侧第一个比当前元素小/大的问题,都可以使用单调栈,线性时间可解。
单调栈是保持栈里的元素有序。
比如 prices = [8,4,6,2,5]。从右向左扫描 prices。
- 第 -1 个元素 5:此时栈为空,说明没有在其右边且不大于它的元素。将 5 入栈。
- 第 -2 个元素 2:此时栈顶为 5,大于 2,把 5 弹出。之后栈变为空,也说明没有在其右边且不大于它的元素。将 2 入栈。这里的关键是 5 的出栈是安全的,因为:
- 如果后续元素小于 2,那么也一定小于 5,5 在这里没用;
- 如果后续元素大于等于 2,2 就是离它最近且不大于它的元素,也不需要考虑 5。
- 第 -3 个元素 6:此时栈顶 2 小于等于 6,说明 2 就是其右边第一个不大于它的元素,即为相应的折扣。然后将 6 入栈(目前栈为
[2, 6])。 - 第 -4 个元素 4:栈顶 6 大于 4,弹出。栈顶变为 2,小于等于 6,说明 2 就是其右边第一个不大于它的元素,即为相应的折扣。将 4 入栈(即
[2, 4])。 - 第 -5 个元素 8:栈顶 4 小于等于 8,即为相应折扣。将 8 入栈(即
[2, 4, 8])。
class Solution:
def finalPrices(self, prices: list[int]) -> list[int]:
stack = []
for i in range(len(prices) - 1, -1, -1):
p = prices[i]
while stack and stack[-1] > p:
stack.pop()
if stack:
prices[i] -= stack[-1]
if not stack or stack[-1] < p:
stack.append(p)
return prices
Another O(n)
上边是逆向扫描数组,还可以正向扫描(从左到右)。
在一个价格右边找第一个不大于它的价格作为折扣。逆向扫描的时候,是把折扣的候选值放在栈中。那么正向扫描时,是把待打折的元素(其实是下标)放在栈中。
- 第 1 个元素 8:此时栈为空,说明它无法作为其他商品的折扣(它左边没有不小于它的元素)。将下标 0 入栈(因为后续还需要使用下标对该位置的元素进行操作)。
- 第 2 个元素 4:此时栈顶价格为 8(下标 0),大于等于 4,说明 4 可以作为其折扣,将其出栈,出栈的同时给对应下标 0 的价格减去当前价格(折扣)4。之后栈为空,将下标 1 入栈。
- 第 3 个元素 6:此时栈顶价格为 4(下标 1),小于 6,说明 6 不能作为其折扣,直接入栈(目前栈为
[1(4), 2(6)])。 - 第 4 个元素 2:此时栈顶价格为 6(下标 2),大于等于 2,说明 2 可以作为其折扣,将其出栈并同时给对应下标 2 的价格减去当前价格(折扣)2。新的栈顶价格为 4(下标 1),依然大于等于 2,说明 2 也可作为其折扣,将其出栈并同时给下标 1 的价格减去当前价格 2。之后栈为空,将下标 3 入栈。
- 第 5 个元素 3:此时栈顶价格为 2(下标 3),小于 3,说明 3 不能作为其折扣,直接入栈(目前栈为
[3(2), 4(3)])。
最后栈里剩下的都是找不到折扣的。
正向扫描优点还挺多的,首先扫描方向更符合直觉,其次代码简洁很多,再次如果做 in-place 修改,修改操作发生在被修改元素(的下标)出栈的时候,修改之后也就不会被访问到,比较安全(节省空间)。而逆向扫描,修改操作发生在入栈的时候,需要注意入栈的应该是修改前的值。但有些场景需要入栈下标(如 739. Daily Temperatures),那么通过下标再引用对应元素值的时候,就要注意应该取到修改前还是修改后的值,从而考虑是否必需开辟额外的存储空间记录修改后的值。
class Solution:
def finalPrices(self, prices: list[int]) -> list[int]:
stack = []
for i, price in enumerate(prices):
while stack and prices[stack[-1]] >= price:
prices[stack.pop()] -= price
stack.append(i)
return prices
评论需要 JavaScript。