企业官网建设流程全解析

# 栈里到底该放什么？用三道 C++ 题练习普通栈与单调栈

知道栈是“后进先出”，还不一定能顺利写出栈题。拿到题目后，更具体的问题是：哪些信息需要留下？新元素到来时，它会用到最近留下的哪一项？

这篇文章用三道题说明栈的不同用途：棒球比赛保存有效历史，逆波兰表达式保存计算结果，每日温度保存等待答案的日期。代码使用 C++17，各段Solution对应一道题，分别提交或编译。

1. 棒球比赛：被取消的记录不能再参与计算

LeetCode 682「棒球比赛」给出一串操作。数字表示新增分数，D表示新增前一个有效分数的两倍，+表示新增前两个有效分数之和，C表示取消前一个有效分数。

例如：

操作：5, 2, C, D, + 5 -> [5] 2 -> [5, 2] C -> [5] D -> [5, 10] + -> [5, 10, 15] 总分：30

这里最容易忽略的是“有效”两个字。处理C后，分数2已经不在记录里，接下来的D应该使用5。

把有效记录按顺序放进栈，每次取消末尾的记录，栈顶就自然恢复为此前的有效分数。对于+，需要同时读取最后两项，而它们仍然保留。使用vector模拟栈，既能在末尾添加和删除，也能直接读取倒数第二项。

#include<numeric>#include<string>#include<vector>usingnamespacestd;classSolution{public:intcalPoints(vector<string>&operations){vector<int>scores;for(conststring&operation:operations){if(operation=="C"){scores.pop_back();}elseif(operation=="D"){scores.push_back(scores.back()*2);}elseif(operation=="+"){intsize=static_cast<int>(scores.size());intnextScore=scores[size-1]+scores[size-2];scores.push_back(nextScore);}else{scores.push_back(stoi(operation));}}returnaccumulate(scores.begin(),scores.end(),0);}};

每次操作结束后，scores都包含当前全部有效分数。这就是检查实现是否正确的依据。例如，["1", "C"]会留下空记录，最后求和得到0。

题目保证操作合法，所以C、D和+都有足够的历史分数，所有中间结果也都在 32 位整数范围内。在这些约束下，处理n个操作的时间复杂度是O(n)，空间复杂度是O(n)；vector的末尾追加按均摊成本计算。

2. 逆波兰表达式：先弹出的是右操作数

LeetCode 150「逆波兰表达式求值」使用后缀表达式：运算符写在操作数之后。

2 1 + 3 * -> (2 + 1) * 3 -> 9 4 13 5 / + -> 4 + (13 / 5) -> 6

数字先入栈。读到运算符时，最近的两个数正好是它需要的操作数。计算完成后，把结果放回栈，供后面的运算继续使用。

以2 1 + 3 *为例：

读取 2： [2] 读取 1： [2, 1] 读取 +： 弹出 1 和 2，计算 2 + 1，压入 3 -> [3] 读取 3： [3, 3] 读取 *： 弹出 3 和 3，计算 3 * 3，压入 9 -> [9]

栈里的3可能是原始数字，也可能是子表达式2 1 +的结果。后续运算只需要这个值，不需要保存原来的表达式。

减法和除法需要留意顺序。对于8 3 -，先弹出的3是右操作数，之后弹出的8是左操作数。答案应为8 - 3 = 5。

#include<stack>#include<string>#include<vector>usingnamespacestd;classSolution{public:intevalRPN(vector<string>&tokens){stack<int>values;for(conststring&token:tokens){boolisOperator=token=="+"||token=="-"||token=="*"||token=="/";if(!isOperator){values.push(stoi(token));continue;}intright=values.top();values.pop();intleft=values.top();values.pop();if(token=="+"){values.push(left+right);}elseif(token=="-"){values.push(left-right);}elseif(token=="*"){values.push(left*right);}else{values.push(left/right);}}returnvalues.top();}};

这段实现还有两个细节：判断运算符时比较完整字符串，因此"-11"会被正确解析为负数；C++17 的整数除法向零截断，-7 / 2得到-3，符合题目要求。

题目保证表达式合法、不会除零，且中间结果可用 32 位整数表示。每个 token 处理一次，在整数长度有界的约束下，时间复杂度为O(n)；多个操作数可能同时等待运算，空间复杂度为O(n)。

3. 每日温度：栈保存还没找到答案的日期

LeetCode 739「每日温度」要求计算每一天之后，还要等几天才会出现更高温度。后面没有更高温度时，答案为0。

温度：[73, 74, 75, 71, 69, 72, 76, 73] 答案：[ 1, 1, 4, 2, 1, 1, 0, 0]

直接的做法是从每一天出发向右查找。温度持续下降时，每一天都会扫描剩余部分，最坏需要O(n²)时间。

可以换一个处理方向：从左到右看当天温度，判断它能为哪些此前的日期确定答案。还没遇到更高温度的日期先放进栈中。

为什么保存下标

题目要的是等待天数。若第i天解决了第previous天，答案就是i - previous。只存温度值无法得到这个距离。

栈中下标从底到顶递增，对应温度从底到顶非递增，允许相等。假设当前等待中的栈是：

下标： 0 1 2 温度：73 71 69 ↑ 栈顶

第 3 天温度为72。它比栈顶的69高，第 2 天得到答案3 - 2 = 1。弹出后继续比较，72也高于71，第 1 天得到答案3 - 1 = 2。接下来栈顶温度为73，当天温度无法解决它，于是停止。

再把第 3 天入栈，栈变为[0:73, 3:72]，仍然保持温度从底到顶非递增。

当前日期为什么是第一个更暖日

一个日期留在栈中，说明此前没有遇到能让它出栈的更高温度。遍历日期按顺序增加，因此第一次触发出栈的日期就是右侧第一个更暖日。

单调性使得比较可以停在栈顶：如果当前温度连栈顶都不超过，那么它也不会超过栈底方向那些更高或相等的温度。

#include<stack>#include<vector>usingnamespacestd;classSolution{public:vector<int>dailyTemperatures(vector<int>&temperatures){intn=static_cast<int>(temperatures.size());vector<int>answer(n,0);stack<int>pendingDays;for(inti=0;i<n;++i){while(!pendingDays.empty()&&temperatures[i]>temperatures[pendingDays.top()]){intprevious=pendingDays.top();pendingDays.pop();answer[previous]=i-previous;}pendingDays.push(i);}returnanswer;}};

while不能随意改成if，因为一天可能解决多个等待中的日期。比较条件必须是严格>：对于[70, 70, 71]，答案是[2, 1, 0]，第二个70不能让第一个70出栈。

两层循环为什么仍是 O(n)

外层循环处理n个日期。内层循环虽然会连续弹出多个下标，但一个下标弹出后就不会再入栈。

整个过程只有n次入栈，最多n次出栈，所以总时间复杂度为O(n)。栈在温度持续下降或全部相等时会保存全部下标，额外空间复杂度为O(n)，返回数组另外占用O(n)空间。

遍历结束时，仍在栈里的日期后面没有更高温度，保留初始化的0即可。

4. 写代码前，先说清楚栈顶的含义

这三道题都使用栈，但保存的内容和出栈条件各不相同：

做一道新栈题时，可以先写一句话描述“每轮结束后，栈里保存什么”。这句话应当在所有操作之后都成立。棒球比赛取消记录后仍只保留有效分数；表达式计算后用一个结果代替两个操作数；每日温度处理完当天后，栈里仍只剩尚未找到更高温度的日期。

容器跟着这些需求选择即可。棒球比赛需要读取末尾两项，使用vector很直接；另外两题只需要栈顶操作，使用std::stack就足够。每个解法只维护必要状态，不必提前设计一套通用框架。

练习时可以拿["1", "C"]、["8", "3", "-"]、["-7", "2", "/"]和[70, 70, 71]手动推演。这几个小输入分别检查空记录、操作数顺序、负数除法和相等温度，能暴露不少模板记忆掩盖的问题。