1. 问题背景与需求解析这道LeetCode 1547题看似简单实则考察了开发者对数组遍历和条件判断的掌握程度。题目要求我们模拟一个商品打折系统给定一个商品价格数组prices对于每个商品我们需要在后续商品中找到第一个价格当前商品价格的商品然后用当前价格减去这个折扣价得到最终价格。如果后续没有满足条件的商品则该商品不打折。举个例子 输入 prices [8,4,6,2,3] 输出 [4,2,4,2,3] 解释商品0价格8后续第一个8的是4(商品1)所以8-44商品1价格4后续没有4的保持4商品2价格6后续第一个6的是2(商品3)所以6-24商品3价格2后续没有2的保持2商品4价格3后续没有商品保持32. 暴力解法与复杂度分析2.1 双重循环实现最直观的解法是使用双重循环def finalPrices(prices): n len(prices) res prices.copy() for i in range(n): for j in range(i1, 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较大时比如n10^5O(n²)的复杂度会导致性能问题。在实际电商系统中商品数量可能非常大这就需要我们寻找更优的解法。3. 单调栈优化解法3.1 单调栈原理单调栈是一种特殊的栈结构它可以帮助我们在O(n)时间内解决下一个更大/更小元素这类问题。对于本题我们需要找到每个元素右边第一个它的元素这正是单调栈的典型应用场景。基本思路维护一个单调递增栈栈底到栈顶元素递增遍历数组对于当前元素当栈不为空且栈顶元素当前元素时说明当前元素是栈顶元素的下一个更小弹出栈顶元素计算折扣重复直到栈为空或不满足条件将当前元素索引入栈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 res3.3 复杂度分析时间复杂度O(n)每个元素最多入栈出栈一次空间复杂度O(n)最坏情况下栈需要存储所有元素实操技巧在实现单调栈时通常存储元素索引而非元素值这样既可以通过索引访问元素值又保留了元素的原始位置信息。4. 边界条件与测试用例4.1 常见边界情况空数组输入应该返回空数组单元素数组直接返回原数组完全递减数组每个元素都能找到折扣如[5,4,3,2,1] → [1,1,1,1,1]完全递增数组没有元素能找到折扣如[1,2,3,4,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 电商系统中的折扣逻辑虽然题目简化了实际场景但核心逻辑与电商系统中的自动比价功能类似。在实际系统中可能还需要考虑折扣限制条件如仅限特定商品类别时间限制如限时折扣组合折扣多件商品共同满足条件会员等级折扣叠加5.2 性能优化思考对于海量商品数据可以考虑分布式计算将商品分片处理预处理对商品按价格排序建立索引缓存对热门商品折扣结果缓存6. 同类问题延伸掌握单调栈解法后可以解决一系列类似问题LeetCode 496 - 下一个更大元素 ILeetCode 503 - 下一个更大元素 IILeetCode 739 - 每日温度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 res7.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 典型错误直接修改原数组应该先创建副本栈中存储元素值而非索引不方便计算忽略等于的情况题目要求而不仅是边界条件处理不当如空数组或单元素数组8.2 调试方法打印栈状态在循环中添加print(stack)小规模测试先用简单例子验证可视化跟踪在纸上画出执行过程我在实际编码中发现使用单调栈时最容易犯的错误是搞混栈的单调方向。对于这个问题我们需要的是下一个当前的元素因此维护的是单调递增栈。如果题目改为找下一个当前的元素则需要使用单调递减栈。
