概述为什么栈是算法题里的基础结构学完二分查找和二分答案之后我们开始进入一类更偏“数据结构思维”的题型栈。栈看起来很简单只支持从一端加入和删除元素。但在算法题里它经常出现在下面这些场景中括号匹配是否合法字符串消除和撤销操作表达式求值函数调用和递归过程寻找左边或右边第一个更大、更小的元素单调栈解决下一个更大元素、每日温度、柱状图面积等问题很多初学者刚学栈时只记住了两个操作push 入栈 pop 出栈但真正做题时关键并不是会不会调用 API而是要理解栈适合处理“最近的、还没有被匹配或解决的元素”。比如括号匹配中最后出现的左括号应该最先被右括号匹配比如单调栈中栈里暂时放着那些“还没找到答案”的元素。这篇文章会围绕三个高频方向展开栈的基本概念和使用方式括号匹配类问题表达式和字符串处理单调栈的基本思想与模板学完这篇你应该能识别“后进先出”“最近匹配”“等待被解决”这几类问题并用栈或单调栈写出清晰的解法。核心概念栈到底是什么栈是一种遵循后进先出规则的数据结构。Last In First Out也就是最后放进去的元素最先被取出来。可以把栈想象成一摞盘子顶部 [ 4 ] - 最后放入最先取出 [ 3 ] [ 2 ] [ 1 ] 底部常见操作有三个操作含义时间复杂度push把元素放入栈顶O(1)pop删除并返回栈顶元素O(1)peek查看栈顶元素但不删除O(1)在 Java 里刷算法题更推荐用Deque来模拟栈而不是老旧的Stack类DequeIntegerstacknewArrayDeque();stack.push(1);// 入栈stack.push(2);stack.push(3);inttopstack.peek();// 查看栈顶3intxstack.pop();// 出栈3为什么不推荐StackJava 里的Stack是比较早期的类继承自Vector很多方法带有同步开销。在算法题中我们通常不需要这些额外特性。所以推荐写法是DequeIntegerstacknewArrayDeque();如果栈里可能存null则不能使用ArrayDeque因为它不允许null元素。不过算法题里几乎不会把null当作正常栈元素所以这个限制通常不是问题。栈不是重点在“能存数据”而是重点在“最后加入的未处理元素最先被处理”。适用场景什么题应该想到栈如果题目中出现下面这些信号可以优先考虑栈匹配关系括号、标签、成对符号最近关系最近一个未被匹配的元素撤销操作输入退格、路径回退、编辑器撤销嵌套结构表达式、函数调用、递归展开单调关系找左边或右边第一个更大、更小的元素可以用一句话判断如果当前元素需要和“前面最近的某个元素”发生关系栈就很可能有用。下面我们从最经典的括号匹配开始。经典题型一括号匹配括号匹配是栈最经典的入门题。题目通常是给定一个只包含(、)、[、]、{、}的字符串判断括号是否有效。有效字符串需要满足左括号必须用相同类型的右括号闭合左括号必须以正确顺序闭合每个右括号都有一个对应的左括号例如()[]{} - true ([{}]) - true (] - false ([)] - false为什么括号匹配适合用栈看这个字符串([{}])扫描过程如下读到 ( 等待匹配入栈 读到 [ 等待匹配入栈 读到 { 等待匹配入栈 读到 } 应该匹配最近的 { 读到 ] 应该匹配最近的 [ 读到 ) 应该匹配最近的 (最后出现的左括号必须最先被匹配。这正好符合栈的后进先出特性。解题思路遍历字符串中的每个字符如果是左括号就入栈如果是右括号栈为空说明没有左括号可以匹配返回false栈顶不是对应的左括号返回false否则弹出栈顶表示匹配成功遍历结束后栈必须为空流程可以表示为遇到左括号入栈等待匹配 遇到右括号检查栈顶是否匹配 最后检查栈是否为空Java 代码实现importjava.util.ArrayDeque;importjava.util.Deque;classSolution{publicbooleanisValid(Strings){DequeCharacterstacknewArrayDeque();for(charc:s.toCharArray()){if(c(||c[||c{){stack.push(c);}else{if(stack.isEmpty()){returnfalse;}charleftstack.pop();if(c)left!(){returnfalse;}if(c]left![){returnfalse;}if(c}left!{){returnfalse;}}}returnstack.isEmpty();}}复杂度分析时间复杂度O(n)每个字符最多入栈一次、出栈一次空间复杂度O(n)最坏情况下所有字符都是左括号常见错误只统计左右括号数量数量相等不代表顺序正确例如([)]遇到右括号时不判断栈空会导致空栈弹出异常遍历结束后不检查栈是否为空例如(((会被误判右括号永远只能匹配“最近的那个还没被匹配的左括号”所以用栈。经典题型二字符串消除与退格模拟除了括号匹配栈还很适合处理“撤销前一个字符”这类问题。例如题目给定字符串s和t其中#表示退格判断两个字符串最终是否相等。示例s ab#c t ad#c s 处理后是 ac t 处理后是 ac 结果为 true为什么可以用栈退格符#的含义是删除前面最近的一个普通字符。这个“最近的一个字符”正好就是栈顶元素。Java 代码实现importjava.util.ArrayDeque;importjava.util.Deque;classSolution{publicbooleanbackspaceCompare(Strings,Stringt){returnbuild(s).equals(build(t));}privateStringbuild(Stringstr){DequeCharacterstacknewArrayDeque();for(charc:str.toCharArray()){if(c#){if(!stack.isEmpty()){stack.pop();}}else{stack.push(c);}}StringBuildersbnewStringBuilder();while(!stack.isEmpty()){sb.append(stack.pop());}returnsb.reverse().toString();}}复杂度分析时间复杂度O(n m)空间复杂度O(n m)其中n和m分别是两个字符串的长度。进一步优化这道题也可以用双指针从后往前扫描把空间复杂度优化到O(1)。但作为栈的入门题用栈模拟过程最直观也最容易写对。当题目要求删除“前面最近的一个有效元素”时栈通常是最自然的模拟方式。经典题型三表达式处理栈在表达式问题中也非常常见。原因是表达式往往存在运算优先级括号嵌套临时结果从左到右扫描时暂时无法立刻计算的内容最典型的例子是计算只包含非负整数、、-、*、/的表达式。例如32*2 - 7为什么表达式可以用栈如果表达式里只有和-从左到右计算比较容易。但一旦有*和/就不能简单地按顺序计算。例如3 2 * 2乘法优先级更高所以应该先算2 * 2。一种常见做法是遇到num把num入栈遇到-num把-num入栈遇到*num弹出栈顶并乘以num再入栈遇到/num弹出栈顶并除以num再入栈最后把栈里所有数相加这样乘除法会被立刻处理加减法被转化成正负数累加。Java 代码实现importjava.util.ArrayDeque;importjava.util.Deque;classSolution{publicintcalculate(Strings){DequeIntegerstacknewArrayDeque();charsign;intnum0;for(inti0;is.length();i){charcs.charAt(i);if(Character.isDigit(c)){numnum*10(c-0);}if((!Character.isDigit(c)c! )||is.length()-1){if(sign){stack.push(num);}elseif(sign-){stack.push(-num);}elseif(sign*){stack.push(stack.pop()*num);}elseif(sign/){stack.push(stack.pop()/num);}signc;num0;}}intans0;while(!stack.isEmpty()){ansstack.pop();}returnans;}}代码关键点num用来拼接多位数字例如123sign表示当前数字前面的运算符遇到新运算符时处理上一个数字最后一个数字后面没有运算符所以需要用i s.length() - 1触发结算复杂度分析时间复杂度O(n)空间复杂度O(n)常见错误没有处理多位数把123当成1、2、3忘记处理空格表达式中可能包含空格最后一个数字没有入栈因为末尾没有运算符触发计算乘除法直接累加会破坏运算优先级栈可以把暂时不能最终结算的数字保存起来并在遇到高优先级运算时及时修正栈顶。进阶概念什么是单调栈普通栈只强调后进先出。而单调栈在此基础上还要求栈内元素保持某种单调性。常见有两类单调递增栈从栈底到栈顶递增单调递减栈从栈底到栈顶递减它经常用来解决对每个元素找它左边或右边第一个比它大或比它小的元素。例如nums [2, 1, 2, 4, 3]如果要找每个元素右边第一个更大的数2 - 4 1 - 2 2 - 4 4 - -1 3 - -1暴力做法是对每个位置向右扫描最坏时间复杂度是O(n^2)。单调栈可以把它优化到O(n)。单调栈的核心思想单调栈里存的不是“已经得到答案”的元素而是还没有找到答案、正在等待被后续元素解决的元素。以“下一个更大元素”为例当前数字num比栈顶元素大说明num就是栈顶元素的下一个更大元素弹出栈顶并记录答案继续比较新的栈顶最后把当前元素入栈等待它自己的答案流程如下遍历当前元素 num 当栈不空并且 num 栈顶对应的值 num 就是栈顶元素的答案 弹出栈顶 当前元素入栈注意单调栈里通常存的是下标而不是值。因为记录答案时需要知道答案应该填到哪个位置。单调栈模板下一个更大元素题目给定数组nums返回每个元素右边第一个比它大的元素。如果不存在返回-1。示例输入nums [2, 1, 2, 4, 3] 输出[4, 2, 4, -1, -1]Java 代码实现importjava.util.ArrayDeque;importjava.util.Arrays;importjava.util.Deque;classSolution{publicint[]nextGreaterElement(int[]nums){intnnums.length;int[]ansnewint[n];Arrays.fill(ans,-1);DequeIntegerstacknewArrayDeque();for(inti0;in;i){while(!stack.isEmpty()nums[i]nums[stack.peek()]){intindexstack.pop();ans[index]nums[i];}stack.push(i);}returnans;}}执行过程示例以nums [2, 1, 2, 4, 3]为例当前下标当前值栈中等待元素发生的事02空2入栈1121不比2大入栈222, 12是1的下一个更大元素342, 24依次解决两个24343不比4大入栈最后仍留在栈里的元素说明右边没有更大元素答案保持-1。复杂度分析时间复杂度O(n)空间复杂度O(n)虽然代码里有while循环但每个下标最多入栈一次、出栈一次。所以总复杂度仍然是线性的。单调栈通过维护一组“还没找到答案的元素”让每个元素只进出栈一次从而把向右查找优化到O(n)。单调栈常见变形单调栈题目看起来变化很多但本质经常是下面四类。目标扫描方向栈的维护方式右边第一个更大元素从左到右当前值大于栈顶时弹出右边第一个更小元素从左到右当前值小于栈顶时弹出左边第一个更大元素从左到右入栈前弹出小于等于当前值的元素左边第一个更小元素从左到右入栈前弹出大于等于当前值的元素这里最容易混淆的是有些题是在“当前元素解决栈顶元素”有些题是在“栈顶元素作为当前元素的答案”。初学阶段不建议死背模板而应该先问清楚两个问题我要找的是左边还是右边我要找的是第一个更大还是第一个更小然后再决定扫描方向和弹栈条件。高频例题每日温度题目给定一个整数数组temperatures表示每天的温度返回一个数组answer其中answer[i]表示第i天之后需要等待几天才会出现更高的温度。如果之后都不会升高返回0。示例输入temperatures [73, 74, 75, 71, 69, 72, 76, 73] 输出[1, 1, 4, 2, 1, 1, 0, 0]这道题本质是对每一天找右边第一个温度更高的日子。所以可以使用单调栈。Java 代码实现importjava.util.ArrayDeque;importjava.util.Deque;classSolution{publicint[]dailyTemperatures(int[]temperatures){intntemperatures.length;int[]ansnewint[n];DequeIntegerstacknewArrayDeque();for(inti0;in;i){while(!stack.isEmpty()temperatures[i]temperatures[stack.peek()]){intindexstack.pop();ans[index]i-index;}stack.push(i);}returnans;}}为什么答案是i - index栈里保存的是还没找到更高温度的日期下标。当第i天温度比栈顶日期更高时说明第 i 天就是 index 这一天右边第一个更高温度的日子等待天数就是i - index复杂度分析时间复杂度O(n)空间复杂度O(n)栈与递归的关系理解栈时也可以顺便理解递归。递归函数调用时系统会维护一个调用栈。每次函数调用都会压入一层栈帧函数执行结束后再弹出。例如voiddfs(intx){if(x0){return;}dfs(x-1);}调用dfs(3)的过程大致是dfs(3) 入栈 dfs(2) 入栈 dfs(1) 入栈 dfs(0) 入栈 dfs(0) 返回并出栈 dfs(1) 返回并出栈 dfs(2) 返回并出栈 dfs(3) 返回并出栈所以递归天然带有栈的特征。后面学习 DFS、树遍历、回溯时这一点会非常重要。常见坑点写栈题时最容易错在哪里1. 出栈前没有判断是否为空错误写法charcstack.pop();如果栈为空会直接抛异常。更稳妥的写法if(stack.isEmpty()){returnfalse;}charcstack.pop();2. 把栈顶方向想反push、pop、peek操作的都是栈顶。如果你用ArrayDeque不要一会儿用push一会儿又用addLast否则很容易把方向搞乱。建议统一使用stack.push(x);stack.pop();stack.peek();3. 单调栈里不知道该存值还是下标如果只需要比较大小可以存值。但大多数题还需要填写答案位置或计算距离所以更推荐存下标。例如每日温度ans[index]i-index;这里必须知道原来的下标所以栈里应该存index。模板总结普通栈与单调栈怎么选普通栈模板适用于括号匹配、退格、字符串消除、表达式模拟等问题。DequeIntegerstacknewArrayDeque();for(intx:nums){if(需要入栈){stack.push(x);}else{if(!stack.isEmpty()){inttopstack.pop();// 根据 top 和当前元素处理逻辑}}}单调栈模板适用于寻找下一个更大、更小元素。intnnums.length;int[]ansnewint[n];DequeIntegerstacknewArrayDeque();for(inti0;in;i){while(!stack.isEmpty()nums[i]nums[stack.peek()]){intindexstack.pop();ans[index]nums[i];}stack.push(i);}这个模板解决的是每个元素右边第一个更大的元素如果题目要找的是更小元素就把比较条件改成nums[i]nums[stack.peek()]总结栈的代码并不复杂难点在于识别题型。你可以记住下面几句话栈的核心特征是后进先出括号匹配看的是最近的左括号退格和消除看的是最近的有效字符表达式处理用栈保存暂时不能最终结算的数单调栈保存的是还没有找到答案的元素单调栈常用于找左边或右边第一个更大、更小的元素如果一道题让你反复寻找“最近的未处理元素”优先想普通栈。如果一道题让你寻找“第一个更大或更小的元素”优先想单调栈。