1. 问题背景与需求解析今天想和大家分享一道LeetCode上比较有意思的题目——1547号商品折扣后的最终价格。这道题看似简单但蕴含着不少编程技巧和算法思想特别适合用来训练数组处理和栈的应用能力。题目描述是这样的给定一个商品价格数组prices其中prices[i]表示第i件商品的价格。对于每个商品我们需要找到其后第一个价格小于或等于该商品价格的商品然后用当前商品价格减去这个折扣价格得到最终价格。如果找不到符合条件的折扣商品则该商品保持原价。举个例子 输入[8,4,6,2,3] 输出[4,2,4,2,3] 解释商品0价格8后面第一个8的是4(索引1)所以8-44商品1价格4后面第一个4的是2(索引3)所以4-22商品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时间复杂度O(n²)空间复杂度O(n)。对于小规模数据可以接受但显然不是最优解。2.2 单调栈优化这道题的经典解法是使用单调栈。单调栈特别适合解决寻找下一个更大/更小元素这类问题。基本思路维护一个单调递增栈从栈底到栈顶递增遍历数组对于当前元素如果栈不为空且当前元素栈顶元素说明找到了栈顶元素的折扣弹出栈顶元素计算折扣后的价格重复上述过程直到不满足条件将当前元素索引入栈2.3 代码实现def finalPrices(prices): stack [] res prices.copy() for i, price in enumerate(prices): while stack and prices[stack[-1]] price: j stack.pop() res[j] prices[j] - price stack.append(i) return res时间复杂度O(n)每个元素最多入栈出栈一次空间复杂度O(n)最坏情况下需要存储所有元素。3. 关键点解析3.1 为什么使用单调栈单调栈之所以高效是因为它利用了问题的特性我们只需要找到下一个满足条件的元素不需要关心更远的元素栈结构可以保持元素的相对顺序方便快速查找通过维护单调性可以确保每次比较都是有效的3.2 边界条件处理有几个边界情况需要注意最后一个元素永远没有折扣后面没有商品了可能存在连续多个相同价格的情况空数组输入应该返回空数组3.3 空间优化如果允许修改原数组可以进一步优化空间def finalPrices(prices): stack [] for i, price in enumerate(prices): while stack and prices[stack[-1]] price: j stack.pop() prices[j] - price stack.append(i) return prices这样空间复杂度可以降到O(1)不考虑输出空间。4. 复杂度分析让我们详细分析一下两种方法的复杂度方法时间复杂度空间复杂度适用场景暴力法O(n²)O(n)数据量小(1000)单调栈O(n)O(n)数据量大(1e5)对于LeetCode的测试用例n通常在1e4量级单调栈的优势非常明显。5. 实际应用场景这类问题在实际开发中有很多应用场景电商平台的实时价格计算金融领域的优惠计算库存管理中的价格调整任何需要基于后续元素决定当前值的场景理解这种算法可以帮助我们更好地处理流式数据中的关联计算。6. 常见错误与调试技巧在实现过程中容易犯的几个错误栈空判断遗漏在while循环中忘记检查stack是否为空索引混淆使用价格比较时用了res数组而非原prices数组边界处理不当没有正确处理最后一个元素的情况调试技巧打印栈的状态和当前处理元素对简单测试用例手动模拟执行过程使用assert检查中间结果7. 算法扩展与变种这道题有几个有趣的变种寻找前一个更小元素反向遍历计算折扣总和而非单个折扣考虑时间限制的折扣滑动窗口多级折扣多个满足条件的折扣例如变种题可能是对于每个商品计算所有后续小于等于它的商品中最大的折扣这就需要稍微修改算法逻辑。8. 不同语言的实现虽然Python实现很简洁但其他语言也有各自的实现特点Java版本public int[] finalPrices(int[] prices) { StackInteger stack new Stack(); int[] res Arrays.copyOf(prices, prices.length); for (int i 0; i prices.length; i) { while (!stack.isEmpty() prices[stack.peek()] prices[i]) { res[stack.pop()] - prices[i]; } stack.push(i); } return res; }C版本vectorint finalPrices(vectorint prices) { stackint s; vectorint res prices; for (int i 0; i prices.size(); i) { while (!s.empty() prices[s.top()] prices[i]) { res[s.top()] - prices[i]; s.pop(); } s.push(i); } return res; }9. 单元测试用例设计好的测试用例应该覆盖各种边界情况test_cases [ ([], []), # 空输入 ([1], [1]), # 单元素 ([5,4,3,2,1], [1,1,1,1,1]), # 递减序列 ([1,2,3,4,5], [1,2,3,4,5]), # 递增序列 ([8,4,6,2,3], [4,2,4,2,3]), # 题目示例 ([10,1,1,6], [9,0,1,6]), # 重复元素 ]10. 性能优化技巧对于特别大的数据集还可以考虑以下优化使用数组模拟栈来减少对象开销并行处理如果问题允许使用更高效的数据结构如双端队列例如用数组模拟栈的Python实现def finalPrices(prices): stack [] res prices.copy() for i, price in enumerate(prices): while stack and prices[stack[-1]] price: j stack.pop() res[j] - price stack.append(i) return res虽然Python中这种优化效果不明显但在C/Java中可能会有显著提升。11. 实际工程应用建议在实际项目中应用此类算法时建议添加详细的注释说明算法逻辑对输入参数进行有效性校验考虑添加日志记录关键步骤提供多种实现方式备选编写完整的单元测试例如一个更健壮的实现可能包含def finalPrices(prices): if not isinstance(prices, list): raise TypeError(Input must be a list) if not all(isinstance(x, (int, float)) for x in prices): raise ValueError(All elements must be numbers) stack [] res prices.copy() for i, price in enumerate(prices): while stack and prices[stack[-1]] price: j stack.pop() res[j] - price stack.append(i) return res12. 算法可视化理解为了更好理解单调栈的工作过程我们可以用以下方式可视化初始数组[8,4,6,2,3]步骤i0, price8栈空push 0栈[0]i1, price4栈顶prices[0]8 4res[0]8-44pop 0push 1栈[1]i2, price6栈顶prices[1]4 6push 2栈[1,2]i3, price2栈顶prices[2]6 2res[2]6-24pop 2栈顶prices[1]4 2res[1]4-22pop 1push 3栈[3]i4, price3栈顶prices[3]2 3push 4栈[3,4]最终res[4,2,4,2,3]13. 相关题目推荐如果想进一步练习类似题目可以尝试下一个更大元素 I下一个更大元素 II每日温度股票价格跨度这些题目都使用了单调栈的思想是很好的延伸练习。14. 个人实现心得在实际实现过程中我有几点体会画图辅助理解非常重要特别是栈的变化过程使用小的测试用例手动模拟可以帮助发现逻辑错误Python中使用enumerate比range(len())更Pythonic保持栈的单调性是关键要清楚维护的是递增还是递减栈处理边界条件如空输入、单个元素能避免很多错误这道题虽然标为简单但很好地训练了我们对数据结构的理解和应用能力。建议初学者多练习这类题目培养算法思维。 LeetCode 1547题解：商品折扣价格计算的单调栈应用
1. 问题背景与需求解析今天想和大家分享一道LeetCode上比较有意思的题目——1547号商品折扣后的最终价格。这道题看似简单但蕴含着不少编程技巧和算法思想特别适合用来训练数组处理和栈的应用能力。题目描述是这样的给定一个商品价格数组prices其中prices[i]表示第i件商品的价格。对于每个商品我们需要找到其后第一个价格小于或等于该商品价格的商品然后用当前商品价格减去这个折扣价格得到最终价格。如果找不到符合条件的折扣商品则该商品保持原价。举个例子 输入[8,4,6,2,3] 输出[4,2,4,2,3] 解释商品0价格8后面第一个8的是4(索引1)所以8-44商品1价格4后面第一个4的是2(索引3)所以4-22商品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时间复杂度O(n²)空间复杂度O(n)。对于小规模数据可以接受但显然不是最优解。2.2 单调栈优化这道题的经典解法是使用单调栈。单调栈特别适合解决寻找下一个更大/更小元素这类问题。基本思路维护一个单调递增栈从栈底到栈顶递增遍历数组对于当前元素如果栈不为空且当前元素栈顶元素说明找到了栈顶元素的折扣弹出栈顶元素计算折扣后的价格重复上述过程直到不满足条件将当前元素索引入栈2.3 代码实现def finalPrices(prices): stack [] res prices.copy() for i, price in enumerate(prices): while stack and prices[stack[-1]] price: j stack.pop() res[j] prices[j] - price stack.append(i) return res时间复杂度O(n)每个元素最多入栈出栈一次空间复杂度O(n)最坏情况下需要存储所有元素。3. 关键点解析3.1 为什么使用单调栈单调栈之所以高效是因为它利用了问题的特性我们只需要找到下一个满足条件的元素不需要关心更远的元素栈结构可以保持元素的相对顺序方便快速查找通过维护单调性可以确保每次比较都是有效的3.2 边界条件处理有几个边界情况需要注意最后一个元素永远没有折扣后面没有商品了可能存在连续多个相同价格的情况空数组输入应该返回空数组3.3 空间优化如果允许修改原数组可以进一步优化空间def finalPrices(prices): stack [] for i, price in enumerate(prices): while stack and prices[stack[-1]] price: j stack.pop() prices[j] - price stack.append(i) return prices这样空间复杂度可以降到O(1)不考虑输出空间。4. 复杂度分析让我们详细分析一下两种方法的复杂度方法时间复杂度空间复杂度适用场景暴力法O(n²)O(n)数据量小(1000)单调栈O(n)O(n)数据量大(1e5)对于LeetCode的测试用例n通常在1e4量级单调栈的优势非常明显。5. 实际应用场景这类问题在实际开发中有很多应用场景电商平台的实时价格计算金融领域的优惠计算库存管理中的价格调整任何需要基于后续元素决定当前值的场景理解这种算法可以帮助我们更好地处理流式数据中的关联计算。6. 常见错误与调试技巧在实现过程中容易犯的几个错误栈空判断遗漏在while循环中忘记检查stack是否为空索引混淆使用价格比较时用了res数组而非原prices数组边界处理不当没有正确处理最后一个元素的情况调试技巧打印栈的状态和当前处理元素对简单测试用例手动模拟执行过程使用assert检查中间结果7. 算法扩展与变种这道题有几个有趣的变种寻找前一个更小元素反向遍历计算折扣总和而非单个折扣考虑时间限制的折扣滑动窗口多级折扣多个满足条件的折扣例如变种题可能是对于每个商品计算所有后续小于等于它的商品中最大的折扣这就需要稍微修改算法逻辑。8. 不同语言的实现虽然Python实现很简洁但其他语言也有各自的实现特点Java版本public int[] finalPrices(int[] prices) { StackInteger stack new Stack(); int[] res Arrays.copyOf(prices, prices.length); for (int i 0; i prices.length; i) { while (!stack.isEmpty() prices[stack.peek()] prices[i]) { res[stack.pop()] - prices[i]; } stack.push(i); } return res; }C版本vectorint finalPrices(vectorint prices) { stackint s; vectorint res prices; for (int i 0; i prices.size(); i) { while (!s.empty() prices[s.top()] prices[i]) { res[s.top()] - prices[i]; s.pop(); } s.push(i); } return res; }9. 单元测试用例设计好的测试用例应该覆盖各种边界情况test_cases [ ([], []), # 空输入 ([1], [1]), # 单元素 ([5,4,3,2,1], [1,1,1,1,1]), # 递减序列 ([1,2,3,4,5], [1,2,3,4,5]), # 递增序列 ([8,4,6,2,3], [4,2,4,2,3]), # 题目示例 ([10,1,1,6], [9,0,1,6]), # 重复元素 ]10. 性能优化技巧对于特别大的数据集还可以考虑以下优化使用数组模拟栈来减少对象开销并行处理如果问题允许使用更高效的数据结构如双端队列例如用数组模拟栈的Python实现def finalPrices(prices): stack [] res prices.copy() for i, price in enumerate(prices): while stack and prices[stack[-1]] price: j stack.pop() res[j] - price stack.append(i) return res虽然Python中这种优化效果不明显但在C/Java中可能会有显著提升。11. 实际工程应用建议在实际项目中应用此类算法时建议添加详细的注释说明算法逻辑对输入参数进行有效性校验考虑添加日志记录关键步骤提供多种实现方式备选编写完整的单元测试例如一个更健壮的实现可能包含def finalPrices(prices): if not isinstance(prices, list): raise TypeError(Input must be a list) if not all(isinstance(x, (int, float)) for x in prices): raise ValueError(All elements must be numbers) stack [] res prices.copy() for i, price in enumerate(prices): while stack and prices[stack[-1]] price: j stack.pop() res[j] - price stack.append(i) return res12. 算法可视化理解为了更好理解单调栈的工作过程我们可以用以下方式可视化初始数组[8,4,6,2,3]步骤i0, price8栈空push 0栈[0]i1, price4栈顶prices[0]8 4res[0]8-44pop 0push 1栈[1]i2, price6栈顶prices[1]4 6push 2栈[1,2]i3, price2栈顶prices[2]6 2res[2]6-24pop 2栈顶prices[1]4 2res[1]4-22pop 1push 3栈[3]i4, price3栈顶prices[3]2 3push 4栈[3,4]最终res[4,2,4,2,3]13. 相关题目推荐如果想进一步练习类似题目可以尝试下一个更大元素 I下一个更大元素 II每日温度股票价格跨度这些题目都使用了单调栈的思想是很好的延伸练习。14. 个人实现心得在实际实现过程中我有几点体会画图辅助理解非常重要特别是栈的变化过程使用小的测试用例手动模拟可以帮助发现逻辑错误Python中使用enumerate比range(len())更Pythonic保持栈的单调性是关键要清楚维护的是递增还是递减栈处理边界条件如空输入、单个元素能避免很多错误这道题虽然标为简单但很好地训练了我们对数据结构的理解和应用能力。建议初学者多练习这类题目培养算法思维。