如何优化LeetCode 2290「到达角落需要移除的最少障碍物」的代码运行速度？

嘿，我刚巧踩过这题的坑！要提速的话，核心得换个更高效的算法思路——这题本质是带权最短路径问题（空地权重0，障碍物权重1，求起点到终点的最小权重和），普通DFS/BFS甚至朴素Dijkstra在大数据量下很容易超时，给你几个实打实的优化方向：

核心优化：用0-1 BFS替代常规算法 #

因为路径的权重只有0（走空地）和1（移除障碍物）两种，0-1 BFS是这类问题的最优解，时间复杂度直接从Dijkstra的O(mn log mn)降到O(mn)，每个节点只访问一次，效率提升明显。它的核心逻辑是用双端队列：

• 遇到权重为0的节点（走空地），加到队列头部，保证优先处理这类“代价低”的路径
• 遇到权重为1的节点（移除障碍物），加到队列尾部

细节优化点 #

• 距离数组优化：用和网格同大小的二维数组dist记录到每个点的最小障碍物移除数，初始设为无穷大（比如int.MaxValue），起点dist[0][0]设为0，只有当新计算的距离比已记录的更小时才更新并加入队列，避免无效操作。
• 提前终止：一旦遍历到终点（右下角），直接返回当前距离，不用走完所有节点，节省时间。
• 方向数组复用：提前定义上下左右四个方向的数组，避免重复代码，也减少内存开销。

优化后的C#代码示例 #

using System;
using System.Collections.Generic;

public class Solution {
    public int MinimumObstacles(int[][] grid) {
        int rows = grid.Length;
        int cols = grid[0].Length;
        
        // 初始化距离数组，用int.MaxValue表示未访问
        int[][] minObstacles = new int[rows][];
        for (int i = 0; i < rows; i++) {
            minObstacles[i] = new int[cols];
            Array.Fill(minObstacles[i], int.MaxValue);
        }
        minObstacles[0][0] = 0;
        
        // 用LinkedList模拟双端队列，C#没有内置Deque
        LinkedList<(int x, int y)> deque = new LinkedList<(int, int)>();
        deque.AddFirst((0, 0));
        
        // 上下左右四个方向
        int[][] directions = new int[][] {
            new int[] {-1, 0}, new int[] {1, 0},
            new int[] {0, -1}, new int[] {0, 1}
        };
        
        while (deque.Count > 0) {
            var current = deque.First.Value;
            deque.RemoveFirst();
            
            // 提前返回终点结果
            if (current.x == rows - 1 && current.y == cols - 1) {
                return minObstacles[current.x][current.y];
            }
            
            foreach (var dir in directions) {
                int newX = current.x + dir[0];
                int newY = current.y + dir[1];
                
                // 检查边界
                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
                    int newObstacleCount = minObstacles[current.x][current.y] + grid[newX][newY];
                    
                    // 只有当新的障碍物数更少时才更新
                    if (newObstacleCount < minObstacles[newX][newY]) {
                        minObstacles[newX][newY] = newObstacleCount;
                        
                        // 空地放队头，障碍物放队尾
                        if (grid[newX][newY] == 0) {
                            deque.AddFirst((newX, newY));
                        } else {
                            deque.AddLast((newX, newY));
                        }
                    }
                }
            }
        }
        
        // 题目保证有路径，这里只是兜底
        return minObstacles[rows - 1][cols - 1];
    }
}

额外说明 #

• C#里没有内置的双端队列，用LinkedList模拟是最方便的，它的AddFirst和RemoveFirst都是O(1)操作，符合0-1 BFS的要求。
• Array.Fill是.NET Core 3.0+支持的方法，比手动循环填充数组更高效，如果是旧版本的话，换成手动循环就行。

备注：内容来源于stack exchange，提问作者MaxH