055 · Final Prices With a Special Discount in a Shop
My First Thoughts
嗯，这题是上题的衍生版本吧，对不对。
这里就一个数组，也就是 prices：
prices = [1, 2, 3, 4, 5]肯定是需要遍历的：
for item in prices:然后实际的解题逻辑是什么呢？
对于每个商品，最终价格由它右边的第一个更小值决定，而且这里的“更小”包含等于。
也就是：如果右边第一个满足条件的价格是 discount，那么当前商品的最终价格就是：
price - discount首先想到需要一个 stack，这个也很自然。
如果栈是空的，就需要把商品放进去，比如第一个：
if not stack:
stack.append(item)然后到了第二个商品，stack 里面已经有一个值了。这个时候就需要判断当前商品是不是比栈最后一个商品更便宜，或者说是不是小于等于栈顶：
if item <= stack[-1]:如果当前商品更便宜，那么栈最后一个数就需要减去当前商品价格：
stack[-1] - item这就是那个商品的最终价格，可以放到 result 里面。
但是这里马上有一个问题：应该怎么放进 result 呢？
因为答案要保持原来的顺序。如果栈里面的元素被弹出，或者一次处理了多个旧商品，那么 result 的顺序就不太好维护。
所以会想到：是不是栈里不应该记录价格本身，而应该记录 index？
这样每个 index 都能回到原数组里的准确位置。当前价格 prices[i] 可以和 prices[stack[-1]] 比较。如果当前价格可以给栈顶商品打折，就直接修改那个位置：
prices[stack[-1]] -= prices[i]然后把这个下标弹出来。
这样代码大概就是：
stack = []
length = len(prices)
for i in range(0, length):
while stack and prices[i] <= prices[stack[-1]]:
prices[stack[-1]] -= prices[i]
stack.pop()
stack.append(i)
return prices最后还留在 stack 里的商品，说明右边没有小于或等于它的价格。它们本来就没有折扣，所以原价不用再处理。
Why That Is Not Enough
这个思路其实已经是正解了。
真正需要补清楚的地方不是算法方向，而是状态含义：
stack里到底保存什么？
一开始如果保存价格本身，比如：
stack.append(item)比较会很方便，但更新答案会麻烦。因为题目要求返回一个和原数组顺序一致的数组，而只保存价格时，我们不知道应该修改原数组里的哪个位置。
所以关键调整是：
stack.append(i)也就是栈里保存下标，而不是价格。
这样比较时用：
prices[i] <= prices[stack[-1]]更新时用：
prices[stack[-1]] -= prices[i]这个状态一旦明确，后面的逻辑就顺了。
Final Idea
用一个栈 stack 保存：
已经看过，但是还没有找到折扣的商品下标。
从左到右遍历 prices。
当走到位置 i 时，当前价格 prices[i] 在栈里所有商品的右边。
如果当前价格小于或等于栈顶商品的价格：
prices[i] <= prices[stack[-1]]说明当前商品就是栈顶商品正在等待的折扣。
于是可以直接更新栈顶商品的最终价格：
prices[stack[-1]] -= prices[i]然后把这个下标弹出：
stack.pop()这里要用 while，不是 if。
因为同一个当前价格可能同时给前面多个商品打折。
比如：
prices = [8, 6, 2]看到 2 时，它既可以给 6 打折，也可以继续给 8 打折。
当当前价格不能继续解决栈顶商品时，就把当前下标放入栈里，等待右边之后的商品：
stack.append(i)遍历结束以后，栈里剩下的下标都没有找到折扣。它们保持原价即可，所以不用额外处理。
Why It Works
栈里保存的是“还没有找到右边第一个小于或等于自己的价格”的商品下标。
从左到右遍历时，当前商品一定在栈里那些商品的右边。
如果当前价格 prices[i] 小于或等于栈顶商品 prices[stack[-1]]，那么当前商品可以作为栈顶商品的折扣。
为什么它是“第一个”满足条件的折扣？
因为栈顶商品从入栈到现在，中间经过的商品都没有把它弹出来。也就是说，中间那些商品都没有满足“小于或等于它”的条件。现在第一次遇到满足条件的 prices[i]，所以它就是右边第一个可用折扣。
弹出栈顶以后，还要继续检查新的栈顶。
这是因为当前商品可能也能给更早的商品打折。
比如：
prices = [8, 4, 6, 2, 3]过程可以理解成：
看到 8：还没有折扣，stack = [0]
看到 4：4 <= 8，所以 8 的最终价格变成 4，stack = []，再放入 4 的下标
看到 6：6 不能给 4 打折，stack = [1, 2]
看到 2：2 <= 6，先给 6 打折；2 <= 4，再给 4 打折；最后放入 2 的下标
看到 3：3 不能给 2 打折，放入 3 的下标最后栈里剩下的是价格 2 和 3 的下标。它们右边没有可以用的折扣，所以保持原价。
得到：
[4, 2, 4, 2, 3]Code
def finalPrices(prices):
stack = []
for i in range(len(prices)):
while stack and prices[i] <= prices[stack[-1]]:
prices[stack[-1]] -= prices[i]
stack.pop()
stack.append(i)
return pricesComplexity
| Time | \(O(n)\) - n 是 prices 的长度；每个下标最多入栈一次、出栈一次 |
| Space | \(O(n)\) - 最坏情况下所有商品都找不到折扣，栈会保存所有下标 |
Takeaway
当题目要求给原数组里的某些位置回填答案时，栈里通常保存下标比保存值更灵活。值用来比较，下标用来准确更新答案位置。
← Quiz