1. 面试算法题解析分糖果问题分糖果问题是面试中常见的贪心算法题型主要考察对问题本质的理解和算法设计能力。典型题目描述如下有一群孩子站成一排每个孩子有一个评分。你需要给这些孩子分发糖果要求每个孩子至少分到一颗糖果评分更高的孩子必须比相邻孩子获得更多糖果这个问题的关键在于理解评分与糖果分配之间的关系。我们先来看一个具体例子假设孩子评分数组为 [1,3,2,2,1]那么最优的糖果分配应该是 [1,2,1,2,1]总共需要7颗糖果。1.1 贪心算法思路解析解决这个问题的核心在于认识到糖果分配需要满足两个方向的约束从左向右看如果右边孩子评分更高则其糖果数必须比左边多从右向左看如果左边孩子评分更高则其糖果数必须比右边多具体实现步骤如下初始化一个全1的糖果数组candies从左向右遍历如果ratings[i] ratings[i-1]则candies[i] candies[i-1]1从右向左遍历如果ratings[i] ratings[i1]则candies[i] max(candies[i], candies[i1]1)最后累加candies数组得到总糖果数def candy(ratings): n len(ratings) candies [1] * n # 从左向右遍历 for i in range(1, n): if ratings[i] ratings[i-1]: candies[i] candies[i-1] 1 # 从右向左遍历 for i in range(n-2, -1, -1): if ratings[i] ratings[i1]: candies[i] max(candies[i], candies[i1]1) return sum(candies)1.2 复杂度分析与边界条件时间复杂度O(n)因为我们进行了两次线性遍历 空间复杂度O(n)需要额外的数组存储糖果数需要注意的边界条件空数组情况所有孩子评分相同的情况严格递增或递减的评分序列提示在实际面试中建议先处理边界条件再实现核心算法逻辑这能展示你的代码健壮性。2. 接雨水问题详解接雨水问题是另一道经典面试题考察对数组操作和双指针技巧的掌握。题目描述如下给定n个非负整数表示每个宽度为1的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。2.1 暴力解法与优化思路最直观的解法是对于每个柱子找到它左右两侧的最高柱子然后取两者中的较小值减去当前柱子的高度就是这个柱子能接的雨水量。def trap_brute(height): res 0 n len(height) for i in range(1, n-1): left_max max(height[:i]) right_max max(height[i1:]) res max(0, min(left_max, right_max) - height[i]) return res这个解法时间复杂度为O(n²)因为对于每个元素都要扫描左右两侧。我们可以通过预处理来优化2.2 动态规划优化预先计算每个位置的左右最大值def trap_dp(height): if not height: return 0 n len(height) left_max [0] * n right_max [0] * n left_max[0] height[0] for i in range(1, n): left_max[i] max(left_max[i-1], height[i]) right_max[-1] height[-1] for i in range(n-2, -1, -1): right_max[i] max(right_max[i1], height[i]) res 0 for i in range(n): res min(left_max[i], right_max[i]) - height[i] return res这样时间复杂度降为O(n)空间复杂度也是O(n)。2.3 双指针终极优化进一步优化空间复杂度到O(1)def trap(height): left, right 0, len(height)-1 left_max right_max 0 res 0 while left right: if height[left] height[right]: if height[left] left_max: left_max height[left] else: res left_max - height[left] left 1 else: if height[right] right_max: right_max height[right] else: res right_max - height[right] right - 1 return res这个解法的关键在于理解对于某个柱子我们只需要知道它左右两侧的最大值中较小的那个。3. 双端队列(deque)的应用双端队列是一种重要的数据结构在解决滑动窗口问题时特别有用。以LeetCode 239题滑动窗口最大值为例3.1 问题描述给定一个数组nums有一个大小为k的滑动窗口从数组的最左侧移动到最右侧。你需要找出每个窗口中的最大值。3.2 单调队列解法使用双端队列维护一个单调递减的队列from collections import deque def maxSlidingWindow(nums, k): q deque() res [] for i, num in enumerate(nums): # 移除超出窗口范围的元素 while q and q[0] i - k: q.popleft() # 维护单调递减队列 while q and nums[q[-1]] num: q.pop() q.append(i) # 当窗口形成后开始记录结果 if i k - 1: res.append(nums[q[0]]) return res这个算法的时间复杂度是O(n)因为每个元素最多被加入和移除队列各一次。3.3 双端队列的其他应用场景实现栈和队列回文检查树的层次遍历实现LRU缓存注意在Python中deque的popleft()操作是O(1)时间而list的pop(0)是O(n)时间这是deque的优势所在。4. 经典排序算法实现与优化排序算法是面试中的基础考点下面介绍几种常见排序算法的实现与优化。4.1 快速排序的优化实现标准快速排序在最坏情况下会退化为O(n²)我们可以通过以下方式优化import random def quick_sort(nums): def partition(left, right): # 随机选择pivot避免最坏情况 pivot_idx random.randint(left, right) nums[pivot_idx], nums[right] nums[right], nums[pivot_idx] pivot nums[right] i left for j in range(left, right): if nums[j] pivot: nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[right] nums[right], nums[i] return i def sort(left, right): if left right: return p partition(left, right) sort(left, p-1) sort(p1, right) sort(0, len(nums)-1) return nums优化点随机选择pivot避免有序数组的最坏情况三路快排处理大量重复元素小数组时切换为插入排序4.2 归并排序的应用归并排序是稳定的O(nlogn)算法特别适合链表排序和外部排序def merge_sort(nums): if len(nums) 1: return nums mid len(nums) // 2 left merge_sort(nums[:mid]) right merge_sort(nums[mid:]) return merge(left, right) def merge(left, right): res [] i j 0 while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res归并排序的扩展应用计算逆序对外部排序处理大文件链表排序的最佳选择4.3 堆排序与优先队列堆排序可以用于解决Top K问题import heapq def heap_sort(nums): heapq.heapify(nums) res [] while nums: res.append(heapq.heappop(nums)) return res def top_k(nums, k): heap nums[:k] heapq.heapify(heap) for num in nums[k:]: if num heap[0]: heapq.heappop(heap) heapq.heappush(heap, num) return heap堆排序的特点时间复杂度O(nlogn)原地排序但不稳定适合处理流式数据在实际面试中理解各种排序算法的适用场景比死记实现更重要。例如数据量小且基本有序插入排序需要稳定性归并排序内存受限堆排序平均性能好快速排序