企业官网建设流程全解析

在算法面试和日常开发中，栈（Stack）是一种极其重要且高频使用的数据结构。今天，我们通过一道经典的 LeetCode 题目，彻底搞懂栈的原理、C++ 中栈的声明与常用函数，以及如何利用“单调栈”将算法效率优化到极致。

题目回顾：LeetCode 1475. 商品折扣后的最终价格

题目描述：
给你一个数组 prices，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的最小下标，如果没有满足条件的 j，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

核心诉求：对于每个元素，找到它右侧第一个小于或等于它的元素。

方法一：暴力解法（朴素思想）

最直观的想法是：对于每一个商品 i，我们都往它的右侧去扫描，找到第一个价格小于等于它的商品 j，然后计算差价。

代码实现（C++）

class Solution { public: vector<int> finalPrices(vector<int>& prices) { int n = prices.size(); for (int i = 0; i < n; i++) { // 从 i+1 开始向右寻找第一个 <= prices[i] 的元素 for (int j = i + 1; j < n; j++) { if (prices[j] <= prices[i]) { prices[i] = prices[i] - prices[j]; break; // 找到了最近的，直接跳出内层循环 } } } return prices; } };

复杂度分析

• 时间复杂度：O(N平方)。最坏情况下（如数组单调递增 [1, 2, 3, 4, 5]），每个元素都要扫描到数组末尾，总比较次数约为N平方/2。当N=50000时，计算量高达 12.5 亿次.
• 空间复杂度：O1。原地修改数组，不需要额外空间。

方法二：单调栈（最优解）

暴力解法之所以慢，是因为我们在寻找右侧第一个更小元素时，进行了大量重复的扫描。
我们可以换一种思路：从右往左遍历，并维护一个数据结构，帮助我们快速找到右侧第一个小于等于当前价格的元素。这个数据结构就是单调栈。

为什么是单调栈？

我们从右向左遍历数组。对于当前价格 prices[i]，我们需要找到它右侧第一个比它小的数。
假设右侧有一些价格，比如 [10, 5, 8]。
如果当前价格是 6，右侧的价格中，10 比 6 大，不可能成为 6 的折扣，而且对于更左侧的元素来说，10 也被 6 挡住了（因为 6 更小且更靠左），所以 10 是“无用”的数据，可以直接丢弃。我们可以用一个栈来维护这些“有用”的数据，保证栈内的元素是单调递增的。

算法流程

1. 初始化一个空栈 st（存储下标）。
2. 从右向左遍历数组 prices。
3. 对于当前元素 prices[i]，如果栈不为空，且栈顶元素对应的价格大于当前价格（prices[st.top()] > prices[i]），说明栈顶元素比当前价格大，不可能成为当前价格的折扣，且对于更左侧的元素来说，当前价格更小且更靠左，所以栈顶元素永远不可能被用到了。直接弹出栈顶。
4. 重复步骤3，直到栈为空或栈顶价格小于等于当前价格。
5. 此时，栈顶元素就是右侧第一个小于等于当前价格的元素。如果栈不为空，更新 prices[i] = prices[i] - prices[st.top()]。
6. 将当前元素的下标 i 压入栈中。
7. 遍历结束后返回 prices。

代码实现（C++）

class Solution { public: vector<int> finalPrices(vector<int>& prices) { int n = prices.size(); stack<int> st; // 存储下标，栈内对应的价格单调递增 // 从右向左遍历 for (int i = n - 1; i >= 0; i--) { // 维护单调栈：弹出比当前价格大的元素 while (!st.empty() && prices[st.top()] > prices[i]) { st.pop(); } // 此时栈顶元素就是右侧第一个 <= prices[i] 的元素 if (!st.empty()) { prices[i] -= prices[st.top()]; } // 将当前下标入栈 st.push(i); } return prices; } };

复杂度分析

• 时间复杂度：O(N)。虽然代码里有一个 while 循环，但每个元素最多只会进栈一次、出栈一次，所以总的操作次数是线性的。
• 空间复杂度：O(N)。最坏情况下（如数组单调递减），栈需要存储所有元素的下标。

核心知识：C++ 中 stack 的声明与常用函数

在 C++ 中，stack 是标准模板库（STL）提供的一种容器适配器。它遵循后进先出（LIFO, Last In First Out）的原则。

1. 引入头文件

#include <stack>

2. 声明一个栈

std::stack<int> st; // 存储 int 类型的栈 std::stack<string> st_str; // 存储 string 类型的栈 std::stack<std::pair<int, int>> st_pair; // 存储键值对的栈

3. 常用成员函数（专业术语与功能）