企业官网建设流程全解析

1. 问题背景与需求解析

今天想和大家分享一道LeetCode上比较有意思的题目——1547号"商品折扣后的最终价格"。这道题看似简单，但蕴含着不少编程技巧和算法思想，特别适合用来训练数组处理和栈的应用能力。

题目描述是这样的：给定一个商品价格数组prices，其中prices[i]表示第i件商品的价格。对于每个商品，我们需要找到其后第一个价格小于或等于该商品价格的商品，然后用当前商品价格减去这个折扣价格，得到最终价格。如果找不到符合条件的折扣商品，则该商品保持原价。

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

• 商品0价格8，后面第一个<=8的是4(索引1)，所以8-4=4
• 商品1价格4，后面第一个<=4的是2(索引3)，所以4-2=2
• 商品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

时间复杂度O(n²)，空间复杂度O(n)。对于小规模数据可以接受，但显然不是最优解。

2.2 单调栈优化

这道题的经典解法是使用单调栈。单调栈特别适合解决"寻找下一个更大/更小元素"这类问题。

基本思路：

1. 维护一个单调递增栈（从栈底到栈顶递增）
2. 遍历数组，对于当前元素：
   • 如果栈不为空且当前元素<=栈顶元素，说明找到了栈顶元素的折扣
   • 弹出栈顶元素，计算折扣后的价格
   • 重复上述过程直到不满足条件
3. 将当前元素索引入栈

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 为什么使用单调栈

单调栈之所以高效，是因为它利用了问题的特性：

1. 我们只需要找到"下一个"满足条件的元素，不需要关心更远的元素
2. 栈结构可以保持元素的相对顺序，方便快速查找
3. 通过维护单调性，可以确保每次比较都是有效的

3.2 边界条件处理

有几个边界情况需要注意：

1. 最后一个元素永远没有折扣（后面没有商品了）
2. 可能存在连续多个相同价格的情况
3. 空数组输入应该返回空数组

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. 复杂度分析

让我们详细分析一下两种方法的复杂度：

对于LeetCode的测试用例，n通常在1e4量级，单调栈的优势非常明显。

5. 实际应用场景

这类问题在实际开发中有很多应用场景：

1. 电商平台的实时价格计算
2. 金融领域的优惠计算
3. 库存管理中的价格调整
4. 任何需要基于后续元素决定当前值的场景

理解这种算法可以帮助我们更好地处理流式数据中的关联计算。

6. 常见错误与调试技巧

在实现过程中，容易犯的几个错误：

1. 栈空判断遗漏：在while循环中忘记检查stack是否为空
2. 索引混淆：使用价格比较时用了res数组而非原prices数组
3. 边界处理不当：没有正确处理最后一个元素的情况

调试技巧：

• 打印栈的状态和当前处理元素
• 对简单测试用例手动模拟执行过程
• 使用assert检查中间结果

7. 算法扩展与变种

这道题有几个有趣的变种：

1. 寻找前一个更小元素（反向遍历）
2. 计算折扣总和而非单个折扣
3. 考虑时间限制的折扣（滑动窗口）
4. 多级折扣（多个满足条件的折扣）

例如，变种题可能是："对于每个商品，计算所有后续小于等于它的商品中最大的折扣"，这就需要稍微修改算法逻辑。

8. 不同语言的实现

虽然Python实现很简洁，但其他语言也有各自的实现特点：

Java版本：

public int[] finalPrices(int[] prices) { Stack<Integer> 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++版本：

vector<int> finalPrices(vector<int>& prices) { stack<int> s; vector<int> 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. 性能优化技巧

对于特别大的数据集，还可以考虑以下优化：

1. 使用数组模拟栈来减少对象开销
2. 并行处理（如果问题允许）
3. 使用更高效的数据结构（如双端队列）

例如，用数组模拟栈的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. 实际工程应用建议

在实际项目中应用此类算法时，建议：

1. 添加详细的注释说明算法逻辑
2. 对输入参数进行有效性校验
3. 考虑添加日志记录关键步骤
4. 提供多种实现方式备选
5. 编写完整的单元测试

例如，一个更健壮的实现可能包含：

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 res

12. 算法可视化理解

为了更好理解单调栈的工作过程，我们可以用以下方式可视化：

初始数组：[8,4,6,2,3]

步骤：

1. i=0, price=8
   • 栈空，push 0
   • 栈：[0]
2. i=1, price=4
   • 栈顶prices[0]=8 >=4
   • res[0]=8-4=4
   • pop 0
   • push 1
   • 栈：[1]
3. i=2, price=6
   • 栈顶prices[1]=4 <6
   • push 2
   • 栈：[1,2]
4. i=3, price=2
   • 栈顶prices[2]=6 >=2
     • res[2]=6-2=4
     • pop 2
   • 栈顶prices[1]=4 >=2
     • res[1]=4-2=2
     • pop 1
   • push 3
   • 栈：[3]
5. i=4, price=3
   • 栈顶prices[3]=2 <3
   • push 4
   • 栈：[3,4]

最终res=[4,2,4,2,3]

13. 相关题目推荐

如果想进一步练习类似题目，可以尝试：

• 496. 下一个更大元素 I
• 503. 下一个更大元素 II
• 739. 每日温度
• 901. 股票价格跨度

这些题目都使用了单调栈的思想，是很好的延伸练习。

14. 个人实现心得

在实际实现过程中，我有几点体会：

1. 画图辅助理解非常重要，特别是栈的变化过程
2. 使用小的测试用例手动模拟可以帮助发现逻辑错误
3. Python中使用enumerate比range(len())更Pythonic
4. 保持栈的单调性是关键，要清楚维护的是递增还是递减栈
5. 处理边界条件（如空输入、单个元素）能避免很多错误

这道题虽然标为简单，但很好地训练了我们对数据结构的理解和应用能力。建议初学者多练习这类题目，培养算法思维。