在算法面试和日常开发中栈Stack是一种极其重要且高频使用的数据结构。今天我们通过一道经典的 LeetCode 题目彻底搞懂栈的原理、C 中栈的声明与常用函数以及如何利用“单调栈”将算法效率优化到极致。题目回顾LeetCode 1475. 商品折扣后的最终价格题目描述给你一个数组 prices其中 prices[i] 是商店里第 i 件商品的价格。商店里正在进行促销活动如果你要买第 i 件商品那么你可以得到与 prices[j] 相等的折扣其中 j 是满足 j i 且 prices[j] prices[i] 的最小下标如果没有满足条件的 j你将没有任何折扣。请你返回一个数组数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。核心诉求对于每个元素找到它右侧第一个小于或等于它的元素。方法一暴力解法朴素思想最直观的想法是对于每一个商品 i我们都往它的右侧去扫描找到第一个价格小于等于它的商品 j然后计算差价。代码实现Cclass Solution { public: vectorint finalPrices(vectorint prices) { int n prices.size(); for (int i 0; i n; i) { // 从 i1 开始向右寻找第一个 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。当N50000时计算量高达 12.5 亿次.空间复杂度O1。原地修改数组不需要额外空间。方法二单调栈最优解暴力解法之所以慢是因为我们在寻找右侧第一个更小元素时进行了大量重复的扫描。我们可以换一种思路从右往左遍历并维护一个数据结构帮助我们快速找到右侧第一个小于等于当前价格的元素。这个数据结构就是单调栈。为什么是单调栈我们从右向左遍历数组。对于当前价格 prices[i]我们需要找到它右侧第一个比它小的数。假设右侧有一些价格比如 [10, 5, 8]。如果当前价格是 6右侧的价格中10 比 6 大不可能成为 6 的折扣而且对于更左侧的元素来说10 也被 6 挡住了因为 6 更小且更靠左所以 10 是“无用”的数据可以直接丢弃。我们可以用一个栈来维护这些“有用”的数据保证栈内的元素是单调递增的。算法流程初始化一个空栈 st存储下标。从右向左遍历数组 prices。对于当前元素 prices[i]如果栈不为空且栈顶元素对应的价格大于当前价格prices[st.top()] prices[i]说明栈顶元素比当前价格大不可能成为当前价格的折扣且对于更左侧的元素来说当前价格更小且更靠左所以栈顶元素永远不可能被用到了。直接弹出栈顶。重复步骤3直到栈为空或栈顶价格小于等于当前价格。此时栈顶元素就是右侧第一个小于等于当前价格的元素。如果栈不为空更新 prices[i] prices[i] - prices[st.top()]。将当前元素的下标 i 压入栈中。遍历结束后返回 prices。代码实现Cclass Solution { public: vectorint finalPrices(vectorint prices) { int n prices.size(); stackint 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 stack2. 声明一个栈std::stackint st; // 存储 int 类型的栈 std::stackstring st_str; // 存储 string 类型的栈 std::stackstd::pairint, int st_pair; // 存储键值对的栈3. 常用成员函数专业术语与功能函数名功能描述push(x)将元素 x压入栈顶入栈。pop()弹出栈顶元素出栈。注意该函数不返回被弹出的元素。top()返回栈顶元素的引用。empty()判断栈是否为空。如果为空返回 true否则返回 false。size()返回栈中元素的个数。
替换指南)
