1. 力扣高频算法题深度解析与实战指南
作为程序员面试的"金标准"，力扣（LeetCode）算法题一直是技术人成长的必经之路。今天我将结合自己刷题500+的经验，深度解析394.字符串解码、739.每日温度、84.柱状图中最大的矩形这三道高频题目。这些题目分别来自字符串处理、单调栈和动态规划等核心算法领域，在字节、腾讯等大厂面试中出现率超过60%。
2. 394.字符串解码：嵌套字符串的展开艺术
2.1 问题本质与核心难点
给定一个类似"3[a2[c]]"的编码字符串，需要展开为"accaccacc"。这类嵌套结构天然适合用栈或递归处理，难点在于：
- 多重嵌套时的状态保存（如遇到"[“需要暂存当前结果）
- 数字可能有多位（不能简单用ASCII判断）
- 需要处理字符、数字、括号三种元素类型
2.2 双栈解法实现细节
def decodeString(s: str) -> str: stack = [] num_stack = [] current_str = "" current_num = 0 for char in s: if char.isdigit(): current_num = current_num * 10 + int(char) elif char == '[': num_stack.append(current_num) stack.append(current_str) current_str = "" current_num = 0 elif char == ']': num = num_stack.pop() prev_str = stack.pop() current_str = prev_str + num * current_str else: current_str += char return current_str关键点：遇到'['时，当前字符串和数字都要入栈；遇到']'时，要同时操作两个栈
2.3 递归解法对比
递归版本更简洁但可能栈溢出：
def decodeString(s, i=0): res = "" while i < len(s) and s[i] != ']': if not s[i].isdigit(): res += s[i] i += 1 else: num = 0 while i < len(s) and s[i].isdigit(): num = num * 10 + int(s[i]) i += 1 i += 1 # skip '[' inner, i = decodeString(s, i) i += 1 # skip ']' res += inner * num return res, i3. 739.每日温度：单调栈的经典应用
3.1 问题建模
给定温度列表[73,74,75,71,69,72,76]，需要返回等待更暖天数[1,1,4,2,1,1,0]。这本质上是找每个元素右边第一个更大数的距离。
3.2 单调栈实现模板
def dailyTemperatures(T): stack = [] res = [0] * len(T) for i in range(len(T)): while stack and T[i] > T[stack[-1]]: prev = stack.pop() res[prev] = i - prev stack.append(i) return res技巧：栈中存储的是下标而非温度值，这样既能比较温度又能计算天数差
3.3 复杂度分析与变种
- 时间复杂度：O(n)，每个元素最多入栈出栈一次
- 空间复杂度：O(n)，最坏情况递减序列全部入栈
- 变种：处理价格跨度、股票波动等问题时同样适用
4. 84.柱状图中最大的矩形：单调栈的极致运用
4.1 暴力解法到最优解演进
- 暴力枚举所有左右边界：O(n²)超时
- 固定高度找最大宽度：O(n²)
- 单调栈优化：O(n)
4.2 单调栈解法精讲
def largestRectangleArea(heights): heights = [0] + heights + [0] # 哨兵节点 stack = [] max_area = 0 for i in range(len(heights)): while stack and heights[i] < heights[stack[-1]]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area注意事项：
- 首尾添加哨兵节点避免边界判断
- 宽度计算是当前i与栈顶下一位的差减一
- 出栈时才计算面积
4.3 可视化理解
以[2,1,5,6,2,3]为例：
- 遇到1时，2出栈，计算2×1=2
- 遇到2时，6和5相继出栈：
- 6的面积：6×(4-2-1)=6
- 5的面积：5×(4-1-1)=10
- 最终最大面积为10
5. 刷题方法论与面试技巧
5.1 同类题目归纳
- 字符串解码类似：385.迷你语法分析器、1087.花括号展开
- 单调栈系列：42.接雨水、907.子数组的最小值之和
- 柱状图变种：85.最大矩形、221.最大正方形
5.2 面试实战建议
- 先明确问题边界（询问面试官）
- 从暴力解法说起，逐步优化
- 手写代码时注意变量命名
- 用测试用例验证（如空输入、极端情况）
5.3 调试技巧
- 字符串解码：打印每次入栈出栈状态
- 单调栈问题：可视化绘制元素进出栈过程
- 柱状图面积：在纸上画出每个步骤的计算方式
这三道题涵盖了算法面试中最关键的栈应用场景。建议在理解的基础上，每个类型至少练习5道相似题目。我在准备面试时，会专门建立错题本记录这类问题的变形和解法规律。比如发现很多单调栈问题都可以通过添加哨兵节点来简化代码，这就是刷题量积累后的模式识别能力。
