1. 问题背景与需求解析

这道LeetCode 1547题看似简单，实则考察了开发者对数组遍历和条件判断的掌握程度。题目要求我们模拟一个商品打折系统：给定一个商品价格数组prices，对于每个商品，我们需要在后续商品中找到第一个价格<=当前商品价格的商品，然后用当前价格减去这个折扣价，得到最终价格。如果后续没有满足条件的商品，则该商品不打折。

举个例子： 输入 prices = [8,4,6,2,3] 输出 [4,2,4,2,3] 解释：

• 商品0价格8，后续第一个<=8的是4(商品1)，所以8-4=4
• 商品1价格4，后续没有<=4的，保持4
• 商品2价格6，后续第一个<=6的是2(商品3)，所以6-2=4
• 商品3价格2，后续没有<=2的，保持2
• 商品4价格3，后续没有商品，保持3

2. 暴力解法与复杂度分析

2.1 双重循环实现

最直观的解法是使用双重循环：

def finalPrices(prices): n = len(prices) res = prices.copy() for i in range(n): for j in range(i+1, n): if prices[j] <= prices[i]: res[i] -= prices[j] break return res

时间复杂度分析：

• 外层循环n次，内层循环平均n/2次
• 总时间复杂度O(n²)
• 空间复杂度O(n)（需要存储结果）

注意：这里使用了prices.copy()而不是直接赋值，因为Python中列表是可变对象，直接赋值会导致修改原数组。

2.2 暴力解法的优化空间

虽然暴力解法简单直接，但当n较大时（比如n=10^5），O(n²)的复杂度会导致性能问题。在实际电商系统中，商品数量可能非常大，这就需要我们寻找更优的解法。

3. 单调栈优化解法

3.1 单调栈原理

单调栈是一种特殊的栈结构，它可以帮助我们在O(n)时间内解决"下一个更大/更小元素"这类问题。对于本题，我们需要找到每个元素右边第一个<=它的元素，这正是单调栈的典型应用场景。

基本思路：

1. 维护一个单调递增栈（栈底到栈顶元素递增）
2. 遍历数组，对于当前元素：
   • 当栈不为空且栈顶元素>=当前元素时，说明当前元素是栈顶元素的"下一个更小"
   • 弹出栈顶元素，计算折扣
   • 重复直到栈为空或不满足条件
3. 将当前元素索引入栈

3.2 代码实现

def finalPrices(prices): n = len(prices) res = prices.copy() stack = [] for i in range(n): while stack and prices[stack[-1]] >= prices[i]: j = stack.pop() res[j] -= prices[i] stack.append(i) return res

3.3 复杂度分析

• 时间复杂度：O(n)，每个元素最多入栈出栈一次
• 空间复杂度：O(n)，最坏情况下栈需要存储所有元素

实操技巧：在实现单调栈时，通常存储元素索引而非元素值，这样既可以通过索引访问元素值，又保留了元素的原始位置信息。

4. 边界条件与测试用例

4.1 常见边界情况

1. 空数组输入：应该返回空数组
2. 单元素数组：直接返回原数组
3. 完全递减数组：每个元素都能找到折扣
   • 如[5,4,3,2,1] → [1,1,1,1,1]
4. 完全递增数组：没有元素能找到折扣
   • 如[1,2,3,4,5] → 原样返回
5. 有重复元素：如[8,4,4,2,3] → [4,2,2,2,3]

4.2 测试代码示例

def test_finalPrices(): assert finalPrices([]) == [] assert finalPrices([5]) == [5] assert finalPrices([8,4,6,2,3]) == [4,2,4,2,3] assert finalPrices([5,4,3,2,1]) == [1,1,1,1,1] assert finalPrices([1,2,3,4,5]) == [1,2,3,4,5] assert finalPrices([8,4,4,2,3]) == [4,2,2,2,3]

5. 实际应用场景扩展

5.1 电商系统中的折扣逻辑

虽然题目简化了实际场景，但核心逻辑与电商系统中的"自动比价"功能类似。在实际系统中，可能还需要考虑：

1. 折扣限制条件（如仅限特定商品类别）
2. 时间限制（如限时折扣）
3. 组合折扣（多件商品共同满足条件）
4. 会员等级折扣叠加

5.2 性能优化思考

对于海量商品数据，可以考虑：

1. 分布式计算：将商品分片处理
2. 预处理：对商品按价格排序建立索引
3. 缓存：对热门商品折扣结果缓存

6. 同类问题延伸

掌握单调栈解法后，可以解决一系列类似问题：

1. LeetCode 496 - 下一个更大元素 I
2. LeetCode 503 - 下一个更大元素 II
3. LeetCode 739 - 每日温度
4. LeetCode 84 - 柱状图中最大的矩形

这些问题的共同特点是都需要寻找数组中元素与相邻元素之间的特定关系，单调栈能够高效地维护这种关系。

7. 编码风格与优化建议

7.1 Pythonic写法

可以进一步简化的写法：

def finalPrices(prices): res, stack = prices.copy(), [] for i, price in enumerate(prices): while stack and prices[stack[-1]] >= price: res[stack.pop()] -= price stack.append(i) return res

7.2 其他语言实现

JavaScript版本：

function finalPrices(prices) { const res = [...prices]; const stack = []; for (let i = 0; i < prices.length; i++) { while (stack.length && prices[stack[stack.length-1]] >= prices[i]) { res[stack.pop()] -= prices[i]; } stack.push(i); } return res; }

8. 常见错误与调试技巧

8.1 典型错误

1. 直接修改原数组：应该先创建副本
2. 栈中存储元素值而非索引：不方便计算
3. 忽略等于的情况：题目要求<=而不仅是<
4. 边界条件处理不当：如空数组或单元素数组

8.2 调试方法

1. 打印栈状态：在循环中添加print(stack)
2. 小规模测试：先用简单例子验证
3. 可视化跟踪：在纸上画出执行过程

我在实际编码中发现，使用单调栈时最容易犯的错误是搞混栈的单调方向。对于这个问题，我们需要的是"下一个<=当前"的元素，因此维护的是单调递增栈。如果题目改为找"下一个>=当前"的元素，则需要使用单调递减栈。