1. 题目拆解先搞清楚括号匹配到底在考什么LeetCode第20题“有效的括号”基本上只要是面过试、刷过题的朋友都绕不开。题目本身不长给定一个只包含(,),{,},[,]的字符串判断字符串是否有效要求左括号必须用相同类型的右括号闭合并且按照正确的顺序闭合空字符串视为有效。乍一看特别简单但实际上这道题是栈这种数据结构的经典入门题考的不是你背没背过答案而是你真不真明白栈的先进后出特性怎么用在字符串匹配上。很多人在这一题上翻车不是因为不会写而是因为没用对思路或者写了但边界条件没考虑全。更关键的是我这次准备刻意绕开STL库不用现成的std::stack自己手写一个栈出来。这个点看起来是给自己找麻烦但实际做完你会发现收获完全是两个量级的。为什么这么说我后面会专门花一整节讲。先看一下题目里容易被忽略的隐藏条件输入字符串只包含括号字符不会有字母数字所以不用做额外过滤括号必须“同类型闭合”意思是(只能配)[只能配]{只能配}不能出现(被]关掉这种情况“正确顺序”这个描述包含了两个层面一是左右括号的配对顺序比如([)]这种是不合法的二是交叉嵌套比如([])合法[(])非法。我们可以先自己举几个例子感受一下()有效()[]{}有效(]无效([)]无效{[]}有效((()))有效((())无效左括号多了())无效右括号多了。这些例子跑一遍大致能猜到这题的关键在于怎么记住“当前最需要被匹配的那个左括号是谁”。这正是栈的活儿。2. 为什么非要不使用STL库自己造一个栈先说结论自己写栈不是装也不是炫技是真的有用。很多刷题的朋友上来就std::stackchar st;几行搞定能过也没毛病。但比赛归比赛工程归工程。我见过好几次实际开发里的类似场景某些嵌入式环境、旧项目、或者对内存分配有严格限制的模块根本不允许你用STL容器因为STL容器默认会走堆内存分配即便很多实现有优化仍然存在不确定性。再一个面试的时候你写std::stack面试官大概率会追问一句“那如果不能用STL你怎么办”这一问就能筛掉很多人。为什么因为很多人只是“会用”stack但没想过stack的底层到底是什么——是一块连续内存加一个栈顶指针还是一个节点一个节点串起来的链表两种方案在不同场景下各有各的取舍。能把这个问题讲清楚的人才算真正理解栈。自己实现stack还有一个额外的好处帮你重新审视C里数组、指针、内存管理、以及类封装这些基础功。写一道算法题顺带把C这些基本功复习了一遍这种效率是刷十道水题都比不上的。所以这一篇我打算分为两条路线都做一遍方案A用数组模拟栈静态数组固定大小方案B用链表实现栈动态节点不限定容量两条路线各有各的适用场景我会把它们的代码、思路、优缺点全部展开讲。说明一下题目本身没有限制不能用STL这里纯粹是自我加码。但如果你是为了快速通过直接用std::stack当然可以。这篇的核心价值在于把两种自定义方式都彻底讲透之后你再去看std::stack的源码或者文档会对它内部到底做了什么有更深的体感。题目的数据范围一般不会太大字符串长度最长也就是几百上千这个量级所以数组方案完全可以扛得住。但写实现的时候我们不能假设“就这么点数据随便搞”要有工程化的意识万一输入长度变成十万、一百万呢数组栈固定1万容量还够不够链表栈虽说不限容量但是每个节点都有额外的指针开销缓存又不友好。这些权衡都要心里有数。3. 方案A数组模拟栈最直观也最可控3.1 思路核心一个数组加一个栈顶指针数组模拟栈的核心结构非常简单一段连续的内存区域——也就是数组用来存放元素一个整数变量作为栈顶指针指向当前栈顶元素的位置。以括号匹配为例栈里存的是char类型。我们把左括号依次压进去遇到右括号就弹出栈顶元素进行配对。如果你画一张图这个过程非常直白字符串: ( [ { } ] ) 过程: 1. 读 ( - 入栈 栈: ( 2. 读 [ - 入栈 栈: ( [ 3. 读 { - 入栈 栈: ( [ { 4. 读 } - 栈顶是 {匹配! 弹出 5. 读 ] - 栈顶是 [匹配! 弹出 6. 读 ) - 栈顶是 (匹配! 弹出 结束: 栈为空 有效再看不合法的情况字符串: ( [ ) ] 1. 读 ( - 入栈 栈: ( 2. 读 [ - 入栈 栈: ( [ 3. 读 ) - 栈顶是 [不等于 ) - 直接判定无效所以匹配的核心逻辑就是遇到左括号入栈遇到右括号检查栈顶是不是对应的左括号如果是就弹出如果不是或者栈已经空了那直接返回false。3.2 写代码之前先想清楚三个问题动手前我通常会先自问三个问题想清楚了再写问题一栈的大小应该定多少如果使用数组必须提前确定大小。定太大浪费内存定太小会溢出。因为题目里字符串是给定的我们可以先拿到字符串的长度n那么栈里最多会有多少个元素极端情况就是字符串全部都是左括号比如(((((((((那栈的最大深度就是n。所以数组大小开n 1是最稳妥的多一个是为了防止一些边界操作上的越界问题或者你习惯从0开始计数、用top指向下一个空位也可以开n。但这里有一个工程上的经验如果我们只有一次性的长度信息直接用n开数组是最优解。如果说想要让这个栈更通用可以在初始化的时候做一个动态扩容机制但这就复杂了。我会在后面的链表方案里解决容量的问题。问题二栈顶指针初始值应该是什么这个看起来是小事但特别容易乱。常见有两种约定约定一top -1表示栈为空。入栈时先top再arr[top] val。出栈时直接返回arr[top--]。约定二top 0表示当前可写入位置。入栈时先arr[top] val再top。出栈时先top--再返回arr[top]。我个人的习惯是用约定一因为判空只需要写top -1逻辑上更“栈空”一些。两种都可以但你要在代码里保持一致不要一会儿用这个一会儿用那个不然debug的时候心态会崩。问题三怎么处理右括号出现时栈为空的情况比如字符串是)(。读第一个字符就是右括号此时栈是空的说明前面没有任何左括号可以和它配对直接返回false。这个判断必须放在取栈顶元素之前否则你访问arr[top]的时候top是-1数组下标越界在C里这是未定义行为可能不报错也可能随机崩溃。这是我见过新手最常见的坑之一。3.3 数组模拟栈的完整代码我先把完整代码贴出来然后一行一行拆开讲#include iostream #include cstring using namespace std; class Stack { private: char* data; int capacity; int top; // 栈顶索引初始为 -1 public: explicit Stack(int size) { capacity size; data new char[capacity]; top -1; } ~Stack() { delete[] data; } bool isEmpty() const { return top -1; } bool isFull() const { return top capacity - 1; } void push(char c) { if (isFull()) { return; // 暂不做扩容题目规模可控 } data[top] c; } char pop() { if (isEmpty()) { return \0; } return data[top--]; } char peek() const { if (isEmpty()) { return \0; } return data[top]; } }; bool isValid(string s) { int n s.size(); Stack stack(n); // 栈的最大深度不可能超过 n for (int i 0; i n; i) { char ch s[i]; // 遇到左括号入栈 if (ch ( || ch [ || ch {) { stack.push(ch); } // 遇到右括号分情况判断 else { if (stack.isEmpty()) { return false; // 右括号来了但栈空直接没得匹配 } char left stack.peek(); // 注意这里先看一眼不急着弹出 if ((ch ) left () || (ch ] left [) || (ch } left {)) { stack.pop(); // 匹配成功弹出去 } else { return false; // 不匹配 } } } return stack.isEmpty(); // 最后栈必须为空才是有效括号 } int main() { string tests[] {(), ()[]{}, (], ([)], {[]}, , (((, ()), ({[]})}; for (auto s : tests) { cout \ s \ - (isValid(s) ? valid : invalid) endl; } return 0; }代码很简单但我这里有几个细节想重点说明push里有一个isFull()判断如果满了就静默返回。这个行为实际应用中不应该这样更合理的做法是扩容或者报错。这里因为大小直接开成了字符串长度最坏情况全左括号也能装下所以不会真正触发。但我建议你留一个判断毕竟这是栈的基本素养。peek()和pop()在栈空的时候返回什么我统一返回了\0。这样如果误用了不至于访问到野指针。面试的时候你甚至可以加一个assert但刷题场景保证运行稳定更重要。匹配的时候用peek()先看再决定是否pop()而不是看到右括号就弹这样可以避免“弹错了再后悔”的情况。虽然在这个逻辑里弹错了也就直接返回false了但先看后弹的写法更清晰。3.4 复杂度分析不能只会写不会算这个题的时间复杂度是 O(n)因为只需要遍历字符串一遍每个字符最多入栈一次、出栈一次。空间复杂度也是 O(n)因为最坏情况下栈里会存下所有左括号。展开讲一下时间上push、pop、peek全是 O(1) 操作循环体内是常数次判断整体 O(n)。空间上我们开了一个长度为 n 的char数组。在C中char占1字节所以空间就是 n 字节。对长度为100万的字符串也就1MB完全没问题。这里的关键是空间不是浪费的而是必须的——如果你不用栈光靠几个计数器是做不了嵌套匹配的。有人可能会想能不能做到 O(1) 空间在只包含一种括号的情况下可以用计数器就行。但题目是三种括号混在一起必须知道“最近的那个左括号是谁”这一点就决定了下限必须是 O(n) 空间。想通这一点你就明白为什么这题是栈的经典题了。4. 方案B链表实现栈动态扩容不求人4.1 为什么还要写一种链表版本数组版本最大的问题是什么容量写死了。如果你提前不知道数据规模或者字符串是实时输入的数组方案就会很尴尬开小了不够用开大了浪费。虽然可以写一个resize函数动态扩容但每次扩容都得new一块更大的内存再整体拷贝这个操作的时间成本是 O(n) 的频繁触发会影响性能。链表方案在接口上完全不需要关心“容量”这个概念因为它天然是动态的来一个元素就new一个节点内存按需分配。当然代价是每个节点多了一个next指针在C里一个指针8字节如果存的是char1字节那单节点实际占用是16字节算上对齐内存开销反而比数组大不少。所以这两种方案没有绝对的谁好谁坏只有“在什么场景下谁更合适”。数组适合提前知道规模、追求缓存命中率的场景链表适合规模不确定、需要灵活伸缩的场景。这也是我在工程里选型时真实的判断逻辑。4.2 链栈的节点定义和基础操作链栈的结构体定义非常简单struct Node { char data; Node* next; };每个节点保存一个字符以及指向下一个节点的指针。栈顶永远指向链表的头节点入栈就是在头部插入一个新节点出栈就是删除头节点。这个设计对应着一种取舍如果用链表头当作栈顶入栈出栈都是 O(1)如果用链表尾当栈顶那你得遍历才能找到尾节点入栈出栈就退化成 O(n) 了。所以一定用头节点作为栈顶这个细节新手很容易踩坑。链栈的类结构如下class LinkedStack { private: Node* stackTop; public: LinkedStack() { stackTop nullptr; } ~LinkedStack() { while (stackTop) { Node* temp stackTop; stackTop stackTop-next; delete temp; } } bool isEmpty() const { return stackTop nullptr; } void push(char c) { Node* newNode new Node{ c, stackTop }; stackTop newNode; } char pop() { if (isEmpty()) { return \0; } char result stackTop-data; Node* temp stackTop; stackTop stackTop-next; delete temp; return result; } char peek() const { if (isEmpty()) { return \0; } return stackTop-data; } };这里有一个C11及以后的语法值得注意new Node{ c, stackTop }是聚合初始化省去了先声明再赋值的麻烦。如果你用的编译器比较老也可以写老式初始化Node* newNode new Node(); newNode-data c; newNode-next stackTop; stackTop newNode;4.3 链栈版括号匹配的完整代码#include iostream using namespace std; struct Node { char data; Node* next; }; class LinkedStack { private: Node* stackTop; public: LinkedStack() { stackTop nullptr; } ~LinkedStack() { while (stackTop) { Node* temp stackTop; stackTop stackTop-next; delete temp; } } bool isEmpty() const { return stackTop nullptr; } void push(char c) { Node* newNode new Node{ c, stackTop }; stackTop newNode; } char pop() { if (isEmpty()) { return \0; } char result stackTop-data; Node* temp stackTop; stackTop stackTop-next; delete temp; return result; } char peek() const { if (isEmpty()) { return \0; } return stackTop-data; } }; bool isValid(string s) { LinkedStack stack; for (char ch : s) { if (ch ( || ch [ || ch {) { stack.push(ch); } else { if (stack.isEmpty()) { return false; } char topChar stack.peek(); if ((ch ) topChar () || (ch ] topChar [) || (ch } topChar {)) { stack.pop(); } else { return false; } } } return stack.isEmpty(); } int main() { string tests[] {(), ()[]{}, (], ([)], {[]}, , (((, ()), ({[]})}; for (auto s : tests) { cout \ s \ - (isValid(s) ? valid : invalid) endl; } return 0; }代码整体和数组版非常像主逻辑完全一致只是底层的栈实现换了。这其实就是“接口不变、实现可换”的封装思想面试时你可以顺着这个点去聊会加分。4.4 链表栈最容易踩的坑内存泄露和析构顺序链栈虽然不用管容量了但引入了新的麻烦内存管理。每次new一个节点都必须保证在合适的时机delete它。C不像Java有垃圾回收new出来的东西不会自动释放。代码里我在三个地方做了处理pop函数里取出数据后立刻把旧头节点delete掉析构函数里用一个循环把剩下的所有节点全部释放假设中途抛异常或者提前返回false栈对象析构时也会自动清理。尤其注意析构函数这个while循环很多人会写成这样~LinkedStack() { while (stackTop) { delete stackTop; // 错误只删了节点没有摘链 stackTop stackTop-next; // 但stackTop已经被delete了访问野指针 } }这个写法是错的。delete stackTop之后stackTop-next这块内存已经不属于你了再去访问就是未定义行为。正确的顺序是先保存下一个节点的地址再删除当前节点再移动指针。while (stackTop) { Node* temp stackTop-next; delete stackTop; stackTop temp; }这个坑我当年面试时踩过一次被面试官当场指出来过丢人。现在写进博客里希望后面的人别再踩。另外还有一个性能上的事链栈的new和delete是动态内存操作频繁调用会有不小的开销。跑LeetCode这种小数据可能看不出来但如果数据量到了百万级链表方案会比数组方案慢不少因为每次push都要走一次系统内存分配。这也是为什么实际工程里能用数组模拟栈就优先用数组除非数据规模确实不稳定。5. 匹配逻辑的三种常见写法对比括号匹配的核心逻辑也就是isValid函数里的那段if-else其实有三种主流写法。我在这边全部列出来大家各取所需。5.1 写法一左括号入栈右括号检查后弹出这就是我前面用的写法思路最直白左括号一律入栈右括号出现时先检查栈顶是否匹配匹配就弹出不匹配就返回false。优点是好理解可读性强几乎不需要注释。缺点是代码里有一长串配对判断看起来稍微有点冗余。5.2 写法二用配对表或者switch如果你觉得三个配对条件排在一起有点长可以考虑用switch加case或者用一个查找表优化。比如这种switch写法for (char ch : s) { if (ch ( || ch [ || ch {) { stack.push(ch); } else { char expected ; switch (ch) { case ): expected (; break; case ]: expected [; break; case }: expected {; break; } if (stack.isEmpty() || stack.peek() ! expected) { return false; } stack.pop(); } }这里有一个细节改进expected初始化的空格永远不会被匹配上如果栈顶是一个左括号但不是expected判断会自然失败。而且代码把“栈空”和“栈顶不匹配”合并成了一个条件逻辑更紧凑。5.3 写法三反向压入右括号这种写法很聪明但需要一定的熟练度才能一下想到遇到左括号时不压左括号本身而是压它对应的右括号。这样遇到右括号时只需要弹出栈顶跟当前字符比对相同就继续不同就报错。代码是这样for (char ch : s) { if (ch () { stack.push()); } else if (ch [) { stack.push(]); } else if (ch {) { stack.push(}); } else { if (stack.isEmpty() || stack.pop() ! ch) { return false; } } } return stack.isEmpty();这种方式的好处是无脑入栈的时候已经转换好了出栈的时候直接拿栈顶可能出现的右括号和当前字符比。匹配逻辑就一个!搞定。代码短很多也不容易把配对关系写岔了。我个人最推荐写法三。它是那种“看了一眼就忘不掉”的思路而且对后续做带优先级的括号问题也有帮助。当然如果你第一次接触先用写法一建立直觉再过渡到写法三也很自然。6. 边界条件与测试用例设计这题有一类错误是“看起来对但一跑就崩”问题几乎都出在边界条件上。我把自己测试时用的用例整理成一个表格建议你照着过一遍测试用例预期结果测试意图true空字符串题目明确算有效()true最基本的一对括号()[]{}true多个不嵌套的括号([)]false交叉不匹配最容易错{[]}true正确的嵌套(((false只有左括号没有右括号)))false只有右括号栈会提前为空((()))true深层嵌套((false中途没有右括号())(false最后一个左括号没闭合({[()]})true完全对称嵌套}{false右括号先出现第一眼可能会觉得“就这些也太简单了”。但你去LeetCode评论区逛一圈会发现很多错误的提交都栽在这些看起来平常的用例上尤其是([)]这种交叉匹配的。我特意把边界情况归类成三组组1空输入和单一括号对。空字符串很多人容易漏虽然题目说了算有效但测试用例里如果你没处理会直接判错。组2嵌套与交叉。里面隐藏了一个常见误区有人会只检查“左括号数量等于右括号数量”就拿([)]来说左右数量相等但这种字符串是无效的。计数器方案在这里直接暴露缺陷。组3单侧多余。左括号多遍历结束了栈还不为空返回false右括号多某个时刻栈空了但还要匹配返回false。这两种情况对应着栈“清空”和“溢出”的两种反向检查点。7. 时间复杂度、空间复杂度的实际体感我说一说复杂的度的“体感”部分这比背公式有用。以字符串长度n 100000为例数组版跑一遍的时间大致在毫秒级链栈版因为有new/delete可能会慢上两三倍甚至更多。空间上数组版就占用100KB100000字节链表版则要200KB往上节点里有一个指针。这些数字不精确但足以让你直观感受两种方案的差异。很多算法题解里只会写“O(n)”但对实际工程来说“常数因子”很关键。同样是O(n)一个for循环和嵌套两个for循环复杂度虽然都是O(n)但实际耗时天差地远。括号匹配这个题循环体里全是常数操作所以即便n很大性能也完全不用担心。这也是为什么我说数组栈在这题里是“更优选”因为两者复杂度相同数组版的常数更小。8. 常见问题与调试技巧实录这块内容是我最想写的部分因为我当年在这题上踩过的坑还真不少。整理成FAQ形式方便后面有人遇到问题直接查。8.1 栈顶指针初始化成0还是-1两种都对关键是配套操作要一致。如果初始化top 0入栈就得先写再移如果初始化top -1先移再写。混用是最容易出错的。8.2 为什么我写数组栈越界了大概率是访问栈顶时没判空。比如右括号是第一个字符栈还是空的你直接stack.data[stack.top]而top是-1数组下标越界。在LeetCode上这个可能是“通过”的因为越界不一定会立刻崩溃但它是未定义行为换个环境可能就崩了。8.3 为什么我的字符串遍历完了栈却不为空说明左括号比右括号多。最后返回stack.isEmpty()这个逻辑不能丢。很多人写到最后直接return true把这种情况漏了。比如(((每个左括号都被压栈但没有右括号来弹出如果直接return true就错了。8.4 链表栈析构为什么会报错十有八九是析构函数写错了用了先delete stackTop再访问stackTop-next的方式。记住先存next再删当前节点。8.5 自定义栈的值类型能不能改成模板可以而且这是面试官很喜欢追问的扩展点。把char改成模板参数T栈就可以装任何类型。真正工程里的栈也一定是模板化的。这里我不展开但你有兴趣完全可以自己改造一下。8.6 为什么建议用peek而不是直接用pop判断因为pop会改变栈的状态如果判断不匹配你还得想办法把元素压回去那是给自己找麻烦。所以判断时用peek确认匹配了再pop这是一个非常基础但重要的设计习惯。9. 如果不用栈还能怎么做在结束之前我想聊一个很有价值的思维题如果题目限制你不能用栈并且只考虑一种括号比如只有小括号你会怎么判断方法很简单用一个计数器。遇到(就1遇到)就-1。任何时刻计数不能小于0最后计数必须等于0。伪代码int count 0; for (char c : s) { if (c () count; else if (c )) { count--; if (count 0) return false; } } return count 0;这种方案是 O(1) 空间比栈方案优。但一旦括号类型增多计数器就失灵了因为它没办法记住最近的那个左括号是什么。三种括号交错时你必须知道优先匹配哪个这天然就是栈的职责。这个对比其实告诉我们一个道理数据结构不是越高级越好而是越匹配需求越好。栈之所以这题能用是因为“最近未匹配的左括号”本质上就是先进后出而计数器之所以能省空间是因为单类型括号根本不需要记录“类型”这个维度。10. 刷完这道题下一步你可以做这些拓展这道题只是栈的敲门砖刷完它之后你可以顺势去练几个同类型的问题趁热打铁把栈的知识点焊牢LeetCode 1047删除字符串中的所有相邻重复项。同样是栈的经典应用但这一题的栈里存的是字符而且出栈条件变成了“相邻且相同”。LeetCode 844比较含退格的字符串。这题利用了栈的“撤销最近操作”特性你在编辑器里按退格键本质上就是一次pop()。LeetCode 232用两个栈实现队列。这题考的是栈和队列两种数据结构的相互转换理解深度直接上一个台阶。LeetCode 155最小栈。要求在常数时间内取到栈中的最小值思路是要开两个栈一个正常存数据另一个存当前最小值。这些题目我只提个方向不展开讲了。等你做完括号匹配再回头看它们会发现栈的适用范围远比你想的广。11. 一些实战小技巧和最终建议这次总结一下自己常用的几个调试手段可能对你有用第一写一个打印栈内容的辅助函数。哪怕只是最简陋的从栈底到栈顶输出一遍在调试嵌套括号场景时也帮助极大。亲眼看到栈里每一步的字符变化比脑内推演可靠得多。第二在代码里加断言assert代替静默处理。比如栈空时调用pop与其返回\0让我们迷失在数据海洋里不如直接assert(false)把问题暴露出来。刷题时可以不用但做工程时这个习惯非常实用。第三养成自己列测试用例的习惯。很多人写完代码直接提交红了再改这样效率低且容易重复犯同样的错。建议先把正例、反例、边界例列成一张表一次性跑完再提交。前面我那张测试表就是参考模板。第四LeetCode上做这道题的时候如果你提交失败一定要看那个失败的用例。它往往比你手写的用例更刁钻记下来下次写类似题的时候你就会自动规避这个坑。最后再分享一个我个人的习惯遇到这种“简单题”我反而会花更多时间去做优化和变体。比如这题有人会用unordered_map存括号映射有人会提前判断字符串长度是奇数直接返回false因为有效括号的长度一定是偶数这是个非常漂亮的剪枝。这些都是加分项面试时从这些细节里能看出一个人刷题的深度。// 引用一个快速剪枝的写法示例 bool isValidFast(string s) { if (s.size() % 2 1) return false; // 长度奇数必不可能全部匹配 // ... 然后进入主逻辑 }这个判断很简单但很多人会忽略。字符串长度为奇数时括号永远不可能两两配对直接返回false就行。它没有改变复杂度但它是非常好的一行“面试亮点”。关于这题的内容我尽力把自己的思考过程、两种实现、边界坑点、调试技巧都写进去了。如果你是从零开始接触这道题希望你能先把数组版代码亲手敲一遍再把链表版敲一遍最后用我给的测试用例跑一遍感受一下两种实现的差别。多花这半小时比单纯看十篇题解都值。