当前位置：首页 > news >正文

深度理解算法和数据结构：栈并非天生存在，而是数组的「思想封装」｜4 道经典题从本质吃透栈与单调栈

news 2026/7/9 14:04:29

前言

在学习栈、队列这类数据结构时，很多人会陷入一个误区：把它们当成固定的 API、死记push/pop/top操作。
但我最近真正想通了一件事 ——数据结构从来不是先有的结构，而是先有的思想。栈并不是什么神奇的黑盒，它本质上就是：我们对数组进行一套「特殊化、有规则的限制操作」后，归纳出来的一种使用方法。
只操作数组尾部
只允许先进后出
不随机访问、不从头遍历
用这套规则解决「匹配、嵌套、等待」类问题
当这种用法被固定、被封装，就成了我们今天说的栈。队列、链表、树，全都是如此：思想先行，结构随后。
带着这个本质认知，我把栈体系最经典的 4 道题全部打通总结。不讲花活，只讲：为什么用栈？栈解决了什么？思想是什么？

一、栈的本质：一句话说透

栈 = 数组 + 限制规则
只操作一端（栈顶 = 数组最后一位）
先进后出、后进先出
不遍历、不回头、不随机访问
天然适合：最近匹配、保存现场、寻找下一个更大元素
你甚至可以不用stack，直接用vector模拟栈，逻辑一模一样。我们用的从来不是栈这个结构，而是它背后的操作思想。

二、经典 4 题全归纳（思路 + 思想 + 代码）

1. 最小栈 —— 栈基础 + 空间换时间

题目：实现能 O (1) 获取最小值的栈。核心思想：栈只能操作栈顶，不能遍历求最小值。所以用辅助栈同步记录最小值，不破坏栈规则。用空间换时间，是栈最经典的基础用法。

详细思路

普通栈的问题：如果直接遍历找最小值，时间复杂度是 O (n)，不符合要求，而且栈不应该被遍历。
核心突破口：我们不能遍历，那就提前存好最小值。
用两个栈：
一个正常存数据 stk
一个辅助栈 minStk，每次 push 时，都把当前最小值压进去
同步操作：数据栈 push，最小栈也 push；数据栈 pop，最小栈也 pop。
这样，最小栈的栈顶永远是当前栈的最小值。
核心思想
栈只能操作栈顶，不能遍历。用空间换时间，在入栈时就记录好最小值，保证 O (1) 获取。

classMinStack{stack<int>stk,minStk;public:MinStack(){minStk.push(INT_MAX);}voidpush(intval){stk.push(val);minStk.push(min(val,minStk.top()));}voidpop(){stk.pop();minStk.pop();}inttop(){returnstk.top();}intgetMin(){returnminStk.top();}};

2. 有效的括号 —— 最近匹配 = 栈天生场景

题目：判断(){}[]是否合法匹配。核心思想：谁最后出现，谁最先匹配 → 完全符合栈规则。左括号入栈，右括号匹配栈顶，匹配成功即出栈。逆序处理、就近匹配，是栈最直观的用途。

详细思路

问题本质：最近匹配。最后出现的左括号，应该最先被匹配。
栈的天生优势：后进先出。
遍历字符串：
遇到左括号：把对应的右括号压入栈
遇到右括号：检查是否和栈顶相同
不同 / 栈空 → 不匹配
相同 → 弹出栈顶
最后栈空 = 完全匹配。
核心思想
谁最后进来，谁最先匹配 → 栈就是为这种问题而生。

boolisValid(string s){stack<char>st;for(charc:s){if(c=='(')st.push(')');elseif(c=='{')st.push('}');elseif(c=='[')st.push(']');else{if(st.empty()||st.top()!=c)returnfalse;st.pop();}}returnst.empty();}

3. 字符串解码 —— 嵌套 = 保存现场

题目：解码3[a]2[bc] → aaabcbc。核心思想：遇到[需要保存当前状态（数字 + 字符串）；遇到]需要恢复现场拼接结果。栈 = 天然断点存储器，所有嵌套问题首选栈。

详细思路

问题难点：嵌套结构。遇到 [ 要暂停当前工作，进入内层；遇到 ] 要回到之前的状态。
栈 = 天然现场保存器。
需要保存两个状态：
数字（倍数）
当前拼接好的字符串
两个栈：
numStk：存倍数
strStk：存之前的字符串
遍历规则：
数字：累计计算
[：保存现场 → 数字和字符串入栈，清空当前变量
]：恢复现场 → 出栈，拼接字符串 = 之前字符串 + 当前字符串 × 次数
字母：直接拼接
核心思想
嵌套问题 = 保存现场 + 恢复现场 → 栈最擅长。

stringdecodeString(string s){stack<string>strStk;stack<int>numStk;string curStr;intcurNum=0;for(chark:s){if(isdigit(k)){curNum=curNum*10+(k-'0');}elseif(k=='['){numStk.push(curNum);curNum=0;strStk.push(curStr);curStr.clear();}elseif(k==']'){intcnt=numStk.top();numStk.pop();string prev=strStk.top();strStk.pop();string temp;for(inti=0;i<cnt;i++)temp+=curStr;curStr=prev+temp;}else{curStr+=k;}}returncurStr;}

4. 每日温度 —— 单调栈：寻找下一个更大元素

题目：寻找下一个更高温度，等待几天？核心思想：暴力 O (n²) 太慢。用栈保存还没找到答案的下标，遇到更大值批量出栈。每个元素只入栈、出栈一次 → O (n) 最优解。栈在这里 = 等待队列。

详细思路

暴力解法：两层循环，对每个数往后遍历找更大值 → O (n²)，超时。
优化目标：一次遍历 O (n)。
核心思想：用栈保存还没找到答案的下标。
栈中存下标，不存温度。
遍历逻辑：
当前温度 > 栈顶温度：
→ 栈顶找到了答案！
→ 计算天数差：i - 栈顶下标
→ 弹出栈顶
→ 继续检查新栈顶（while 循环）
直到不能再处理，把当前下标压入栈，等待未来处理
栈始终保持单调递减，栈顶最小。
核心思想
栈 = 等待队列。每个元素只入栈、出栈一次，时间复杂度 O (n)

vector<int>dailyTemperatures(vector<int>&temp){intn=temp.size();vector<int>res(n,0);stack<int>st;for(inti=0;i<n;i++){while(!st.empty()&&temp[i]>temp[st.top()]){intpre=st.top();st.pop();res[pre]=i-pre;}st.push(i);}returnres;}