LeetCode 解題筆記：1840. Maximum Building Height

作者：王一哲
日期：2026年6月20日


LeetCode 題目連結：1840. Maximum Building Height

解題想法

困難題。一開始看到題目，直覺上很想要對答案二分搜，這個寫法需要檢測當時代入的高度 mid 是否符合限制條件，但是我寫不出有效率的檢測方法。比較簡單而且直接的作法分為以下 4 個步驟：

1. 補足兩端的限制條件。因為第1棟建築物高度為 0，restrictions 補上 [1, 0]。將 restrictions 由小到大排序，如果排序後最後一組條件不是第 n 棟建築物，再補上一組最寬鬆的條件 [n, n-1]。
2. 由左到右掃過一輪，更新右側的限制。假設左側的位置及高度分別為 left, hL，右側的位置及高度分別為 right, hR，右側的高度取 hR 及 hL + right - left 較小者。
3. 由右到左掃過一輪，更新左側的限制。假設左側的位置及高度分別為 left, hL，右側的位置及高度分別為 right, hR，左側的高度取 hL 及 hR + right - left 較小者。
4. 由左到右掃過一輪，更新最大高度 imax。假設左側的位置及高度分別為 left, hL，右側的位置及高度分別為 right, hR，兩側之間最大高度為 peak = (hL + hR + right - left) / 2，如果 peak 大於 imax 則更新 imax 為 peak。

Python 程式碼

Runtime: 223 ms, beats 86.36%. Memory: 46.64 MB, beats 20.45%.

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        /* 補足兩端的限制條件 */
        restrictions.push_back({1, 0});  // 第一棟建築物高度 0
        sort(restrictions.begin(), restrictions.end());  // 排序
        // 如果最後一個限制條件不是第 n 棟建築物，補上最寬鬆的條件
        if (restrictions.back()[0] != n) {
            restrictions.push_back({n, n-1});
        }
        
        /* 由左到右，更新右側的限制 */
        int m = (int)restrictions.size();
        for(int i = 1; i < m; i++) {
            int left = restrictions[i-1][0], hL = restrictions[i-1][1];
            int right = restrictions[i][0], hR = restrictions[i][1];
            restrictions[i][1] = min(hR, hL + right - left);
        }
        
        /* 由右到左，更新左側的限制 */
        for(int i = m-2; i >= 0; i--) {
            int left = restrictions[i][0], hL = restrictions[i][1];
            int right = restrictions[i+1][0], hR = restrictions[i+1][1];
            restrictions[i][1] = min(hL, hR + right - left);
        }
        
        /* 掃過所有的條件找最大高度 */
        int imax = 0;
        for(int i = 1; i < m; i++) {
            int left = restrictions[i-1][0], hL = restrictions[i-1][1];
            int right = restrictions[i][0], hR = restrictions[i][1];
            int peak = (hL + hR + right - left) / 2;
            imax = max(imax, peak);
        }
        return imax;
    }
};

C++ 程式碼

Runtime: 95 ms, beats 16.67%. Memory: 106.75 MB, beats 38.89%.

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        /* 補足兩端的限制條件 */
        restrictions.push_back({1, 0});  // 第一棟建築物高度 0
        sort(restrictions.begin(), restrictions.end());  // 排序
        // 如果最後一個限制條件不是第 n 棟建築物，補上最寬鬆的條件
        if (restrictions.back()[0] != n) {
            restrictions.push_back({n, n-1});
        }
        
        /* 由左到右，更新右側的限制 */
        int m = (int)restrictions.size();
        for(int i = 1; i < m; i++) {
            int left = restrictions[i-1][0], hL = restrictions[i-1][1];
            int right = restrictions[i][0], hR = restrictions[i][1];
            restrictions[i][1] = min(hR, hL + right - left);
        }
        
        /* 由右到左，更新左側的限制 */
        for(int i = m-2; i >= 0; i--) {
            int left = restrictions[i][0], hL = restrictions[i][1];
            int right = restrictions[i+1][0], hR = restrictions[i+1][1];
            restrictions[i][1] = min(hL, hR + right - left);
        }
        
        /* 掃過所有的條件找最大高度 */
        int imax = 0;
        for(int i = 1; i < m; i++) {
            int left = restrictions[i-1][0], hL = restrictions[i-1][1];
            int right = restrictions[i][0], hR = restrictions[i][1];
            int peak = (hL + hR + right - left) / 2;
            imax = max(imax, peak);
        }
        return imax;
    }
};