华为 OD 机试动态规划与双指针算法实战

1. 动态规划与双指针在华为 OD 机试中的重要性

华为 OD 机试向来以算法题为核心考察点，其中动态规划和双指针算法出现的频率尤其高。就拿最近几场机试来说，'找车位'和'高效的任务规划'这两道动态规划题几乎成了必考题，而双指针也经常以各种变体形式出现。

为什么华为这么偏爱这两种算法？从实际开发场景来看，动态规划特别适合解决资源优化类问题，比如任务调度、路径规划等华为业务中的常见需求。而双指针在数据处理、字符串操作等基础场景中效率极高。例如经典的'滑动窗口求最大平均数'，本质上就是双指针的变种。

2. 动态规划实战：停车位问题详解

2.1 问题描述与建模

'找车位'问题的典型描述是：给定一个只包含 0 和 1 的数组，1 表示已有车辆停放，0 表示空位。要求找到一个停车位，使得该位置到最近车辆的距离最大。比如数组 [1,0,0,0,1,0,1]，最优解是下标 2 的位置，此时最近距离为 2。

这个问题可以分解为两个子问题：

1. 从左向右遍历，记录每个位置左侧最近的 1 的距离
2. 从右向左遍历，记录每个位置右侧最近的 1 的距离

最终结果是这两个距离中的较小值，再取所有位置中的最大值。这种'分解子问题 + 组合结果'的思路就是动态规划的典型特征。

2.2 代码实现与优化

def max_parking_distance(spaces):
    n = len(spaces)
    left = [float('inf')] * n
    right = [float('inf')] * n
    
    # 从左向右扫描
    last = -float('inf')
    for i in range(n):
        if spaces[i] == 1:
            last = i
        left[i] = i - last
    
    # 从右向左扫描
    last = float('inf')
    for i in range(n - 1, -1, -1):
        if spaces[i] == 1:
            last = i
        right[i] = last - i
    
    # 计算最大最小距离
    max_dist = 0
    for i in range(n):
        dist = min(left[i], right[i])
         dist > max_dist:
            max_dist = dist
     max_dist