1. 贪心算法基础概念解析贪心算法Greedy Algorithm是一种在每一步选择中都采取当前状态下最优决策的算法策略。这种短视的行为模式使得算法在局部最优解的选择上具有高效性但需要特别注意其全局最优解的保证条件。1.1 贪心算法的核心特征贪心算法具有三个典型特征局部最优选择在每一步决策时只考虑当前信息下的最优选择无后效性当前选择不会影响后续子问题的结构问题可分解问题能够分解为相互独立的子问题典型的贪心算法应用场景包括霍夫曼编码数据压缩Dijkstra算法最短路径最小生成树Prim/Kruskal算法任务调度问题零钱兑换问题1.2 贪心算法的适用条件贪心算法要能保证获得全局最优解必须满足以下两个性质贪心选择性质问题的整体最优解可以通过一系列局部最优选择达到最优子结构问题的最优解包含其子问题的最优解以经典的活动选择问题为例假设有一组活动每个活动有开始和结束时间如何选择最多的互不冲突的活动贪心策略是按照结束时间排序每次选择结束最早且不与已选活动冲突的活动。def activity_selection(start, finish): n len(finish) selected [0] last_finish finish[0] for i in range(1, n): if start[i] last_finish: selected.append(i) last_finish finish[i] return selected2. 单调栈技术详解单调栈Monotonic Stack是一种特殊的栈结构其中的元素保持严格的单调性递增或递减。这种数据结构特别适合解决下一个更大元素类的问题。2.1 单调栈的基本原理单调栈的核心操作规则元素入栈前弹出所有破坏单调性的栈顶元素元素入栈后栈内元素保持严格单调性以每日温度问题为例给定每日温度列表计算每天需要等待多少天才能遇到更暖和的温度。def daily_temperatures(T): stack [] result [0] * len(T) for i, temp in enumerate(T): while stack and T[stack[-1]] temp: prev stack.pop() result[prev] i - prev stack.append(i) return result2.2 单调栈的典型应用场景下一个更大元素找出数组中每个元素右边第一个比它大的元素柱状图最大矩形计算柱状图中能勾勒出的最大矩形面积接雨水问题计算二维地形能接住的雨水总量滑动窗口最大值优化滑动窗口中的最大值查找3. 贪心与单调栈的结合应用在实际问题中贪心算法和单调栈经常结合使用。一个典型例子是去除重复字母问题给定一个字符串去除重复字母使得每个字母只出现一次同时保证结果的字典序最小。3.1 问题分析与解法该问题的解决需要同时运用贪心思想在保证后续仍有该字符的前提下选择字典序最小的字符单调栈维护结果字符串的字典序def remove_duplicate_letters(s): counter collections.Counter(s) stack [] seen set() for char in s: counter[char] - 1 if char in seen: continue while stack and char stack[-1] and counter[stack[-1]] 0: seen.remove(stack.pop()) stack.append(char) seen.add(char) return .join(stack)3.2 性能对比分析算法类型时间复杂度空间复杂度适用场景纯贪心O(n^2)O(1)问题简单约束少贪心单调栈O(n)O(n)需要维护顺序的问题4. 实战案例与优化技巧4.1 最大矩形面积问题给定一个仅包含0和1的二维矩阵找出只包含1的最大矩形面积。这个问题可以通过逐行应用单调栈技巧来解决。def maximal_rectangle(matrix): if not matrix: return 0 max_area 0 dp [0] * len(matrix[0]) for row in matrix: for j in range(len(row)): dp[j] dp[j] 1 if row[j] 1 else 0 stack [-1] for i in range(len(dp)): while stack[-1] ! -1 and dp[stack[-1]] dp[i]: h dp[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area4.2 常见错误与调试技巧边界条件处理始终考虑空输入、单元素等边界情况单调性维护确保比较运算符方向正确 还是 索引管理在弹出元素时正确计算宽度等衍生值性能优化预处理数据减少重复计算调试提示在单调栈算法中可以打印栈状态和中间结果来验证算法执行过程。例如在每日温度问题中可以跟踪每天的温度比较和结果更新情况。5. 高级应用与变种问题5.1 反悔贪心算法反悔贪心Regret Greedy是贪心算法的进阶版本允许在后续步骤中反悔之前的选择。典型应用包括任务调度中的延迟任务处理投资组合优化带权区间调度实现反悔贪心的关键是使用优先队列堆来记录可能被反悔的选择。def schedule_course(courses): courses.sort(keylambda x: x[1]) max_heap [] time 0 for duration, end in courses: if time duration end: heapq.heappush(max_heap, -duration) time duration elif max_heap and -max_heap[0] duration: time duration heapq.heappop(max_heap) heapq.heappush(max_heap, -duration) return len(max_heap)5.2 多维单调栈问题当问题扩展到多维空间时单调栈的应用需要相应调整。例如三维柱状图表面积问题需要在行、列两个维度上应用单调栈思想。def trap_rain_water(heightMap): if not heightMap: return 0 m, n len(heightMap), len(heightMap[0]) heap [] visited [[False]*n for _ in range(m)] # 初始化边界 for i in range(m): for j in [0, n-1]: heapq.heappush(heap, (heightMap[i][j], i, j)) visited[i][j] True for j in range(1, n-1): for i in [0, m-1]: heapq.heappush(heap, (heightMap[i][j], i, j)) visited[i][j] True directions [(-1,0),(1,0),(0,-1),(0,1)] res 0 while heap: h, x, y heapq.heappop(heap) for dx, dy in directions: nx, ny xdx, ydy if 0nxm and 0nyn and not visited[nx][ny]: res max(0, h - heightMap[nx][ny]) heapq.heappush(heap, (max(h, heightMap[nx][ny]), nx, ny)) visited[nx][ny] True return res在实际编码面试中理解这些算法的核心思想比死记硬背模板更重要。建议从简单问题入手逐步构建对贪心选择和单调维护的直觉再挑战更复杂的变种问题。