C++实战笔记（2）: 栈

1. 基础知识栈Stack是一种非常经典的线性数据结构它最核心的特点是后进先出Last In First Out, LIFO。也就是说最后进入栈的元素会最先被取出而最早进入的数据反而要等到上面的元素全部弹出后才能访问。这个规律非常符合现实中的很多场景比如一摞叠起来的书最后放上去的书一定最先拿走。在 C 中标准库直接提供了stack容器适配器本质上它不是一个独立实现的底层容器而是对已有线性容器默认deque进行了一层“只允许栈式操作”的封装。也就是说你不能像vector一样随机访问中间元素只能对栈顶进行操作这也是它能天然保证“后进先出”的根本原因。#include stack using namespace std; stackint st;这里的stackint表示定义一个整型栈后续所有操作都围绕栈顶展开。对于栈来说真正需要重点掌握的是几个高频接口push()表示入栈pop()表示出栈top()用于访问栈顶元素empty()判断是否为空size()获取当前元素数量。2. 代码实战2.1. 力扣20题有效的括号给定一个只包括(){}[]的字符串s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。解题思路核心思想就是利用栈的后进先出特性来处理“最近未匹配左括号”。因为括号是否合法本质上要求每一个右括号都必须和它前面最近出现的同类型左括号匹配。这和栈顶元素的访问方式天然一致所以栈是最优数据结构。解题做法从左到右遍历字符串遇到左括号就直接入栈因为它暂时还没有找到匹配对象如果遇到右括号就说明要开始匹配此时必须检查当前栈顶是否是对应类型的左括号。为了提高匹配效率我们再额外使用一个哈希表建立) - ( } - { ] - [这样的映射关系这样每次遇到右括号时都能O(1)判断应该匹配什么左括号。那综上所述整个解题流程可以总结为三个步骤首先遍历字符串其次判断当前字符是不是右括号如果是就检查栈顶是否匹配若是左括号直接入栈最后遍历结束后只要栈为空就说明所有括号全部成功配对完整代码#include stack // 栈用于保存左括号 #include string // 字符串处理 #include unordered_map // 哈希表建立括号映射关系 using namespace std; class Solution { public: bool isValid(string s) { //定义一个字符栈用于存放左括号 stackchar brackerStack; //定义右括号到左括号的映射关系,其中key为右括号value为对应的左括号 unordered_mapchar,char brackerMap { {), (}, {}, {}, {], [} }; //遍历字符串中的每个字符 for (char c : s) { //如果是右括号遍历哈希表中的key找对应值如果是左括号是找不到值的 if(brackerMap.find(c) ! brackerMap.end()) { //情况1栈为空说明没有左括号可以匹配 if(brackerStack.empty()){ return false; } //情况2栈顶元素与当前右括号对应的左括号不匹配 if(brackerStack.top() ! brackerMap[c]) { return false; } //情况3匹配成功弹出栈顶元素 brackerStack.pop(); }else{ //如果是左括号直接入栈 brackerStack.push(c); } } return brackerStack.empty(); //如果栈为空说明所有括号都匹配成功 } };2.2. 力扣394字符串解码给定一个经过编码的字符串返回它解码后的字符串。编码规则为:k[encoded_string]表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。此外你可以认为原始数据不包含数字所有的数字只表示重复的次数k例如不会出现像3a或2[4]的输入。测试用例保证输出的长度不会超过105。解题思路整体思路可以概括为从左到右遍历字符串用一个整数num记录当前重复次数用一个字符串currentStr记录当前层已经解析出的结果当遇到数字时持续累积位数解决12[a]这种多位数字情况当遇到左括号[时说明要进入新的一层嵌套此时需要把当前次数和当前字符串同时入栈保存现场然后清空开始处理括号内部内容当遇到右括号]时说明当前层解析结束此时弹出上一层保存的状态将当前字符串重复指定次数后拼接回去如果是普通字母则直接追加到当前字符串末尾。解题步骤左括号保存现场右括号恢复现场并展开字符串完整代码#include stack #include string #include cctype using namespace std; class Solution { public: string decodeString(string s) { // 数字栈保存每一层括号前的重复次数 stackint numStack; // 字符串栈保存进入括号前上一层已经构造好的字符串 stackstring strStack; int num 0; // 当前解析到的数字 string currentStr ; // 当前层正在构造的字符串 // 遍历整个输入字符串,根据不同字符进行处理 for (char c : s) { // 如果是数字累积重复次数处理多位数 if (isdigit(c)) { num num * 10 (c - 0); } // 遇到左括号保存当前状态 else if (c [) { numStack.push(num); // 保存重复次数 strStack.push(currentStr); // 保存上一层字符串 // 进入新层清空当前状态 num 0; currentStr ; } // 遇到右括号开始展开当前层字符串 else if (c ]) { int repeatTimes numStack.top(); numStack.pop(); string previousStr strStack.top(); strStack.pop(); // 当前层字符串重复 repeatTimes 次 string temp ; for (int i 0; i repeatTimes; i) { temp currentStr; } // 拼接回上一层 currentStr previousStr temp; } // 普通字符直接加入当前字符串 else { currentStr c; } } return currentStr; } };2.3. 力扣739每日温度给定一个整数数组temperatures表示每天的温度返回一个数组answer其中answer[i]是指对于第i天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用0来代替。解题思路整个过程的核心可以总结成一句话栈中保存还没找到更高温度的下标一旦当前温度更高就替栈顶那一天结算答案。完整代码#include vector #include stack using namespace std; class Solution { public: vectorint dailyTemperatures(vectorint temperatures) { // 获取温度数组长度 int n temperatures.size(); // 定义结果数组初始化全部我呢0 // 如果某一天后面没有更高的温度就保持为0 vectorint answer(n,0); //定义一个栈用来存放还没有找到更高温度的下标 stackint s; // 遍历每天温度 for (int i 0; i n; i){ while (!s.empty() temperatures[i] temperatures[s.top()]) { // 取出栈顶下标 int topIndex s.top(); s.pop(); // 计算等待天数当前下标 - 栈顶下标 answer[topIndex] i - topIndex; } // 当前下标入栈表示它暂时还没找到更高温度 s.push(i); } //返回结果数组 return answer; } };2.4. 力扣155最小栈设计一个支持pushpoptop操作并能在常数时间内检索到最小元素的栈。实现MinStack类:MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素解题思路这道题最关键的要求不是普通的push / pop / top而是新增了一个getMin()要在 O(1) 时间返回当前最小值。如果每次调用getMin()都去遍历整个栈时间复杂度就是 O(n)O(n)O(n)显然不符合题目要求。因此这题的核心思想就是使用两个栈同步维护。其中一个主栈dataStack正常存储所有元素另一个辅助栈minStack专门存储“当前阶段的最小值”。解题步骤每次push(val)时主栈一定直接入栈而辅助栈只在以下两种情况入栈辅助栈为空当前元素小于等于辅助栈栈顶最小值这样就能保证辅助栈的栈顶永远是当前所有元素中的最小值。当执行pop()时如果主栈弹出的元素刚好等于当前最小值那么辅助栈也必须同步弹出这样新的最小值就自然变成辅助栈新的栈顶。完整代码#include stack using namespace std; class Minstack { private: //主栈正常存储所有元素 stackint datastack; //辅助栈存储当前最小元素 stackint minstack; public: //构造函数 Minstack(){ } //入栈,如果辅助栈为空或者当前值小于等于当前最小值就同步压入辅助栈 void push(int x) { datastack.push(x); if (minstack.empty() || x minstack.top()) { minstack.push(x); } } // 出栈 void pop() { if (!datastack.empty()) { if (datastack.top() minstack.top()) { minstack.pop(); } datastack.pop(); } } // 获取栈顶元素 int top() { return datastack.top(); } // 获取当前最小值 int getMin() { return minstack.top(); } };