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

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, i0): 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×12遇到2时6和5相继出栈6的面积6×(4-2-1)65的面积5×(4-1-1)10最终最大面积为105. 刷题方法论与面试技巧5.1 同类题目归纳字符串解码类似385.迷你语法分析器、1087.花括号展开单调栈系列42.接雨水、907.子数组的最小值之和柱状图变种85.最大矩形、221.最大正方形5.2 面试实战建议先明确问题边界询问面试官从暴力解法说起逐步优化手写代码时注意变量命名用测试用例验证如空输入、极端情况5.3 调试技巧字符串解码打印每次入栈出栈状态单调栈问题可视化绘制元素进出栈过程柱状图面积在纸上画出每个步骤的计算方式这三道题涵盖了算法面试中最关键的栈应用场景。建议在理解的基础上每个类型至少练习5道相似题目。我在准备面试时会专门建立错题本记录这类问题的变形和解法规律。比如发现很多单调栈问题都可以通过添加哨兵节点来简化代码这就是刷题量积累后的模式识别能力。