【栈】LC 739.每日温度

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接39.每日温度2、题目描述二、个人思路整理1、思路分析核心思路单调递减栈维护一个单调递减栈从栈底到栈顶温度单调递减栈中存储的是数组下标方便直接计算下标差天数。正向遍历数组设当前下标为i温度为temperatures[i]。比较与出栈如果当前温度temperatures[i]大于栈顶下标对应的温度temperatures[st.top()]说明找到了栈顶那一天右侧第一个更高温度的天气。弹出栈顶下标prevIndex st.top()。更新结果ans[prevIndex] i - prevIndex。继续与新的栈顶元素比较直到栈为空或当前温度不大于栈顶温度。入栈将当前下标i压入栈中。初始化返回数组ans初始全填0这样栈中最后遗留的元素即未来没有更高温度的天数自然保留为0。2、解题代码classSolution{public:stringdecodeString(string s){// countStack 用于保存外层括号对应的重复倍数 kstackintcountStack;// strStack 用于保存遇到 [ 之前已经构建好的外层字符串前缀stackstringstrStack;// curStr 记录当前括号层级内累计解码出的字符串string curStr;// curNum 记录紧随其后的 [ 内内容的重复次数支持多位数intcurNum0;for(charc:s){if(isdigit(c)){// 1. 遇到数字按十进制左移累加处理如 100 等多位数情况curNumcurNum*10(c-0);}elseif(c[){// 2. 遇到左括号代表进入新的嵌套层级需要对当前状态进行“存档”countStack.push(curNum);// 保存当前层要重复的次数strStack.push(curStr);// 保存进入括号前累积的前缀字符串// 重置临时变量用于解析新括号内部的数字和字符curNum0;curStr;}elseif(c]){// 3. 遇到右括号当前层级闭合开始“读档”并完成展开拼接intkcountStack.top();// 获取该层字符串需重复的次数countStack.pop();string prevstrStack.top();// 取出进入本层前的外层前缀strStack.pop();// 将本层解析得到的 curStr 重复拼接 k 次string temp;while(k--){tempcurStr;}// 将展开后的内容追加到外层前缀后面更新当前层状态curStrprevtemp;}else{// 4. 普通字母直接追加到当前层级的字符串中curStrc;}}// 遍历结束curStr 即为最终完全解码后的字符串returncurStr;}};复杂度分析时间复杂度O ( n ) O(n)O(n)。每个下标最多入栈一次、出栈一次。空间复杂度O ( n ) O(n)O(n)。最坏情况下如温度严格递减栈需要存放所有下标。三、知识风暴栈Stack是本题的核心数据结构。它遵循「后进先出LIFO」原则配合「单调栈」思想可以高效解决「寻找下一个更大元素」这类问题。理解单调栈的维护规则与出栈时机对掌握本题至关重要。算法核心思想单调递减栈本题维护的是一个从栈底到栈顶温度严格递减的栈。栈中存放的是数组下标而非温度值这样既能通过下标计算天数差又能通过下标回查对应温度进行比较。出栈即结算当遇到一个比栈顶温度更高的新温度时说明栈顶那一天的「下一个更高温度」已经出现此时弹出栈顶并结算结果ans[prevIndex] i - prevIndex。每个元素入栈一次、出栈一次整体时间复杂度为O ( n ) O(n)O(n)。栈底到栈顶的单调性栈内下标对应的温度从栈底到栈顶严格递减。这意味着栈顶元素永远是「当前尚未找到更高温度」且温度最低的那一天一旦出现更高温度栈顶会率先被弹出。常见对比单调栈 vs 暴力解法暴力解法对每一天向后遍历寻找更高温度时间复杂度O ( n 2 ) O(n^2)O(n2)在数据量较大时会超时。单调栈迭代每个元素仅入栈、出栈各一次时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)是解决「下一个更大元素」类问题的标准高效做法。共同点两者都需要比较温度大小。区别在于暴力解法重复扫描了大量无效区间而单调栈利用栈的单调性让每个元素只被比较有限次数从而大幅降低复杂度。“单调栈”设计思想核心思想当需要寻找「右侧第一个更大/更小元素」时可以用单调栈维护一个有序序列。新元素入栈前先弹出所有「被它打败」的栈顶元素这些被弹出的元素恰好就是「找到了答案」的元素。与本题的联系栈中保存的是下标比较时通过下标回查温度。当temperatures[i] temperatures[st.top()]时栈顶下标对应的那一天就找到了右侧第一个更高温度立即结算并弹出。注意事项栈中保存的是下标而非温度值这样可以直接用下标差计算天数同时比较温度时要通过下标回查数组避免下标与温度混淆。使用要点入栈时机当前温度不大于栈顶温度时将当前下标压入栈中保持栈的单调递减性质。出栈时机当前温度大于栈顶温度时弹出栈顶下标并结算ans[prevIndex] i - prevIndex然后继续与新的栈顶比较直到栈空或当前温度不大于栈顶温度。初始化技巧返回数组ans初始全填0这样栈中最后遗留的元素即未来没有更高温度的天数自然保留为0无需额外处理。结果返回遍历结束后栈中剩余的下标对应的天数其ans值保持初始的0直接返回ans即可。算法变体与扩展下一个更大元素LeetCode 496用单调栈求每个元素右侧第一个更大元素是本题的简化版。下一个更大元素 IILeetCode 503循环数组版本通过「翻倍数组」或「取模」技巧处理环形结构。柱状图中最大的矩形LeetCode 84用单调栈维护递增序列快速定位左右边界是单调栈的进阶用法。接雨水LeetCode 42用单调栈按层计算可接雨水量是单调栈在面积/容量计算中的经典应用。相关 LeetCode 例题496. 下一个更大元素 I单调栈 下一个更大元素503. 下一个更大元素 II单调栈 循环数组84. 柱状图中最大的矩形单调栈 边界定位42. 接雨水单调栈 容量计算