# 栈里到底该放什么用三道 C 题练习普通栈与单调栈知道栈是“后进先出”还不一定能顺利写出栈题。拿到题目后更具体的问题是哪些信息需要留下新元素到来时它会用到最近留下的哪一项这篇文章用三道题说明栈的不同用途棒球比赛保存有效历史逆波兰表达式保存计算结果每日温度保存等待答案的日期。代码使用 C17各段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模拟栈既能在末尾添加和删除也能直接读取倒数第二项。#includenumeric#includestring#includevectorusingnamespacestd;classSolution{public:intcalPoints(vectorstringoperations){vectorintscores;for(conststringoperation:operations){if(operationC){scores.pop_back();}elseif(operationD){scores.push_back(scores.back()*2);}elseif(operation){intsizestatic_castint(scores.size());intnextScorescores[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。#includestack#includestring#includevectorusingnamespacestd;classSolution{public:intevalRPN(vectorstringtokens){stackintvalues;for(conststringtoken:tokens){boolisOperatortoken||token-||token*||token/;if(!isOperator){values.push(stoi(token));continue;}intrightvalues.top();values.pop();intleftvalues.top();values.pop();if(token){values.push(leftright);}elseif(token-){values.push(left-right);}elseif(token*){values.push(left*right);}else{values.push(left/right);}}returnvalues.top();}};这段实现还有两个细节判断运算符时比较完整字符串因此-11会被正确解析为负数C17 的整数除法向零截断-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]仍然保持温度从底到顶非递增。当前日期为什么是第一个更暖日一个日期留在栈中说明此前没有遇到能让它出栈的更高温度。遍历日期按顺序增加因此第一次触发出栈的日期就是右侧第一个更暖日。单调性使得比较可以停在栈顶如果当前温度连栈顶都不超过那么它也不会超过栈底方向那些更高或相等的温度。#includestack#includevectorusingnamespacestd;classSolution{public:vectorintdailyTemperatures(vectorinttemperatures){intnstatic_castint(temperatures.size());vectorintanswer(n,0);stackintpendingDays;for(inti0;in;i){while(!pendingDays.empty()temperatures[i]temperatures[pendingDays.top()]){intpreviouspendingDays.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]手动推演。这几个小输入分别检查空记录、操作数顺序、负数除法和相等温度能暴露不少模板记忆掩盖的问题。