← 返回博客列表
VO Meta

Meta VO 真題複盤｜最小水位斷開等高線圖 + 二分查找完整解析

2026-03-16

Meta VO 真題複盤｜最小水位斷開等高線圖 + 二分查找完整解析

導讀：Meta 的 VO 面試經常考察 Grid + Graph Connectivity 的深度理解。「最小水位斷開等高線圖」是一道經典題目，考察候選人對圖論、二分查找、單調性的理解，以及如何從問題建模到優化的完整思路。

本文深度複盤這道真題，包括問題建模、關鍵觀察、算法設計、複雜度分析，以及如何處理大規模資料的優化方案。

📌 題目描述

問題陳述

給定一個網格地形圖，其中每個格子有一個高度值。在左上角是起點（S），右下角是終點（E），兩者的高度都是無窮大。

目標：找到最小的水位，使得起點和終點之間不存在任何路徑。

移動規則：

示例

S 5 4 5 5
4 2 5 1 1
5 5 2 1 5
2 3 2 4 4
5 4 5 5 E

水位變化過程：

水位 = 1 時：

.....
...XX
...X.
.....
.....

水位 = 2 時：

.....
.X.XX
..XX.
.X.X.
.....

水位 = 3 時：

.....
.X.XX
..XX.
XXX..
.....

答案：3（水位達到 3 時，S 和 E 斷開）

🎯 問題建模

關鍵觀察 1：圖論建模

這是一個 二維網格圖：

關鍵觀察 2：單調性

核心性質：隨著水位升高，可走的格子只會越來越少。

數學表述：

結論：答案具有 單調性，可以使用二分查找。

💡 算法設計

方案 1：二分查找 + BFS（標準解法）

class Solution:
    def minimumWaterHeight(self, grid):
        """
        找到最小水位斷開起點和終點
        
        時間複雜度：O(m*n*log(max_height))
        空間複雜度：O(m*n)
        """
        m, n = len(grid), len(grid[0])
        max_height = max(max(row) for row in grid)
        
        def can_reach(water_level):
            """檢查在給定水位下是否能從起點到達終點"""
            if grid[0][0] <= water_level or grid[m-1][n-1] <= water_level:
                return False
            
            visited = [[False] * n for _ in range(m)]
            queue = [(0, 0)]
            visited[0][0] = True
            
            while queue:
                x, y = queue.pop(0)
                
                if x == m - 1 and y == n - 1:
                    return True
                
                # 四個方向
                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nx, ny = x + dx, y + dy
                    
                    if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                        # 只能走高度 > water_level 的格子
                        if grid[nx][ny] > water_level:
                            visited[nx][ny] = True
                            queue.append((nx, ny))
            
            return False
        
        # 二分查找最小水位
        left, right = 0, max_height
        result = max_height
        
        while left <= right:
            mid = (left + right) // 2
            
            if can_reach(mid):
                # 還能到達，水位需要更高
                left = mid + 1
            else:
                # 無法到達，記錄答案並嘗試更低的水位
                result = mid
                right = mid - 1
        
        return result

# 測試
grid = [
    [float('inf'), 5, 4, 5, 5],
    [4, 2, 5, 1, 1],
    [5, 5, 2, 1, 5],
    [2, 3, 2, 4, 4],
    [5, 4, 5, 5, float('inf')]
]

solution = Solution()
print(solution.minimumWaterHeight(grid))  # 輸出：3

方案 2：Union-Find + 逆向思考（優化方案）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        
        return True

def minimumWaterHeightUnionFind(grid):
    """
    使用 Union-Find 的優化方案
    
    思路：反向思考 - 從高到低逐步「淹沒」格子
    當 Start 和 End 斷開時，就是答案
    
    時間複雜度：O(m*n*log(m*n))
    空間複雜度：O(m*n)
    """
    m, n = len(grid), len(grid[0])
    
    # 收集所有高度並排序
    heights = []
    for i in range(m):
        for j in range(n):
            if grid[i][j] != float('inf'):
                heights.append((grid[i][j], i, j))
    
    heights.sort()
    
    uf = UnionFind(m * n)
    start_idx = 0
    end_idx = m * n - 1
    
    # 從低到高逐步添加格子
    for height, i, j in heights:
        idx = i * n + j
        
        # 檢查四個鄰居
        for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ni, nj = i + di, j + dj
            
            if 0 <= ni < m and 0 <= nj < n:
                nidx = ni * n + nj
                
                # 如果鄰居已經被添加（高度更低），則連接
                if grid[ni][nj] < height or grid[ni][nj] == float('inf'):
                    uf.union(idx, nidx)
        
        # 檢查是否斷開
        if uf.find(start_idx) != uf.find(end_idx):
            return height
    
    return max(max(row) for row in grid)

📊 複雜度分析

方案 時間複雜度 空間複雜度 說明
二分 + BFS O(mnlog H) O(m*n) 標準解法，H = max_height
Union-Find O(mnlog(m*n)) O(m*n) 大規模資料優化

🎓 面試要點總結

關鍵知識點

✅ 問題建模 - 從地形圖到圖論問題
✅ 單調性觀察 - 識別二分查找的可用性
✅ 連通性判斷 - BFS/DFS 的應用
✅ 優化思路 - Union-Find 的逆向應用

Follow-up 問題

🚀 VO 面試輔助策略

VO 面試

📚 相關資源

官方資源

學習資源

社區討論

💼 需要專業輔助？

oavoservice 提供專業的 Meta VO 輔助服務：

✅ VO 輔助 - 實時提供思路和代碼提示
✅ 面試代面 - 資深工程師全程陪同
✅ 系統設計輔導 - 幫助你理解大廠思維
✅ 模擬面試 - 提前適應面試環境

聯絡方式

為尽快聯絡和評估，請注明：

發布日期：2026年3月16日
難度：⭐⭐⭐⭐⭐ (困難)
標籤：Meta, VO代做, VO輔助, 面試代面, 二分查找, 圖論, 連通性, 系統設計

更新歷史：