力扣高频算法题解析：字符串解码与单调栈实战

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, i

3. 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 暴力解法到最优解演进

  1. 暴力枚举所有左右边界：O(n²)超时
  2. 固定高度找最大宽度：O(n²)
  3. 单调栈优化：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

注意事项：

  1. 首尾添加哨兵节点避免边界判断
  2. 宽度计算是当前i与栈顶下一位的差减一
  3. 出栈时才计算面积

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 面试实战建议

  1. 先明确问题边界（询问面试官）
  2. 从暴力解法说起，逐步优化
  3. 手写代码时注意变量命名
  4. 用测试用例验证（如空输入、极端情况）

5.3 调试技巧

  • 字符串解码：打印每次入栈出栈状态
  • 单调栈问题：可视化绘制元素进出栈过程
  • 柱状图面积：在纸上画出每个步骤的计算方式

这三道题涵盖了算法面试中最关键的栈应用场景。建议在理解的基础上，每个类型至少练习5道相似题目。我在准备面试时，会专门建立错题本记录这类问题的变形和解法规律。比如发现很多单调栈问题都可以通过添加哨兵节点来简化代码，这就是刷题量积累后的模式识别能力。