Leetcode每日一题 —— 1840. 最高建筑高度

开发调优
,
1

今天上了些强度。

思路

首先，注意到题目输入规模可能较大，n 可能达到 10^9，也就是说从 1 到 n 单趟扫描都是难以接受的，显然我们应该按 restrictions 去处理。

题目给的限制：

  1. id=1 的建筑高度必须是 0（相当于首个限制点）
  2. 相邻两栋高度差不能超过 1
  3. 受 restrictions 中限制点限制的 id 处建筑高度不能超过指定限制

如果没有限制点，就 1, 2 两点说，我们让建筑高度不断递增其实就行了，这个时候 id 差就是两个建筑间的高度差。因为相邻高度差不能超过 1，显然两个建筑间的最大高度差（或最大高度变化量）就是 id 差。

因为规模可能很大，我们只能按 restrictions 中的限制点进行处理：

  • 每个限制点处建筑的最大高度受 \mathrm{maxHeight}_i 以及左右相邻建筑的高度约束
  • 要知道左右相邻建筑的高度约束情况，我们需要从左往右，从右往左扫描处理restrictions，找到每个限制点的实际最大高度限制

先对 restrictions 按 id 排序，按两个方向扫描：

  • 从左往右时，设当前限制点编号是 \mathrm{id}_i，限制高度是 \mathrm{maxHeight}_i，上一个限制点编号和高度分别为 prevId, prevH。根据上面的分析，两点之间最多能在 prevH 的基础上增长 \mathrm{id}_i - \mathrm{prevId} 这么多高度，而此处最大高度又受 \mathrm{maxHeight}_i 限制，因此此处的实际最大高度更新为： \min(\mathrm{prevH}+\mathrm{id}_i - \mathrm{prevId},\ \mathrm{maxHeight}_i)
  • 从右往左同理，继续在上一趟扫描的基础上更新每个限制点的最大高度。只不过最大增加高度的计算是 \mathrm{prevId}-\mathrm{id}_i

这样两趟扫描后，我们可以找到每个限制点的实际最大高度，但是距离结果还差点，我们还需要知道限制点之间部分的最大高度。

根据上面的分析可以知道两个限制点的 id 差就是他们之间最大高度变化量，必然是 \ge 两点间的高度差绝对值的：

  • 显然 id 差等于高度差绝对值时，直接取两个限制点中高度更高的即可
  • 如果 id 差大于高度差的绝对值，我们还可以越过两个限制点间更大的高度，往上继续走一部分，然后再落回来，形成一个“峰”。既然要能落回来，所以最大高度是 两点间最大高度 + 多余部分 \div 2

最后别忘了，最后一个限制点不一定是 n，如果不是的话，我们需要把最后一段按高度递增来处理。

代码

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        // 每个建筑的高度会受相邻建筑的影响
        // 注意不是每栋建筑都有高度限制
        // 问题来了，n 可能非常大，直接扫描 1...n 的话线性时间复杂度都难说
        // 那么只能从 restrictions 上下手了
        // 先对 restrictions 排序
        sort(restrictions.begin(),restrictions.end(),[&](const vector<int>& a,const vector<int>& b){
            return a[0]<b[0];
        });
        // 从第一栋建筑开始，因为高度差不能超过 1，在遇到限制前建筑可以呈非递减的高度趋势
        // 同理从最后一栋建筑向前，建筑高度也是取决于遇到的限制点

        // 左往右、右往左扫描，存每个限制点处的实际最大高度
        int rN=restrictions.size();
        int prevId=1; // 上一个限制点的 ID
        int prevH=0; // 上一个限制点的最大高度
        for(int i=0;i<rN;i++){
            // 因为是非递减，距离上一个限制点的高度，最多能增长 id_i - prevId
            restrictions[i][1]=min(restrictions[i][1],prevH+restrictions[i][0]-prevId);
            prevId=restrictions[i][0];
            prevH=restrictions[i][1];
        }
        // 此时 prevId = 最后一个限制点 ID
        // 题目只限制首个建筑的高度最后一个限制点，最后一个限制点之后的高度递增就行了
        for(int i=rN-2;i>=0;i--){
            // 从倒数第二个开始处理
            restrictions[i][1]=min(restrictions[i][1],prevH+prevId-restrictions[i][0]);
            prevId=restrictions[i][0];
            prevH=restrictions[i][1];
        }
        // 现在知道每个限制点的实际高度限制了
        // 需要考虑限制点之间的情况
        prevId=1;
        prevH=0;
        int res=0;
        for(auto& r:restrictions){
            // 计算两个限制点之间的高度差绝对值
            int hDiff=abs(r[1]-prevH);
            // 计算 ID 差
            int idDiff=r[0]-prevId;
            // hDiff 肯定小于 idDiff，因为两 id 间最多大高度差是 idDiff
            // 上一个限制点高度是 prevH，现在这个限制点高度是 r[1]
            // 两限制点相距 idDiff，也就是其间的高度变化最多可以是 idDiff
            // 如果这个高度变化能超出 hDiff，则 idDiff-hDiff 这部分可能形成一个“峰”
            // 但是既然是“峰”，涨上去后我们还需要能跌回来，因此还要 /2
            // 因此两个限制点间能达到的最大高度就是 max(prevH,r[1])+(idDiff-hDiff)/2
            res=max(res, max(prevH,r[1])+((idDiff-hDiff)>>1));
            prevId=r[0];
            prevH=r[1];
        }
        // 如果最后一个限制点不是 n，那么还要收尾
        res=max(res,prevH+n-prevId);
        return res;
    }
};
4 Likes
2

存在限制点，则对于两个相邻限制点（中间无限制点间隔）的最大高度则为 ( 限制点1最大高度 + 限制点2最大高度 + 1（每次增长最大1，相当于斜率） * 两点间隔 ) /2

于是转为排序（方便直接处理相邻的两个限制点）后求出所有限制点

求出所有限制点，题目的第一个限制点[1,0]不在restrictions中，所以需要额外处理 ，同时所有建筑的高度不能超过左右两栋建筑+1（斜率），也就是增长限制，对于不再restrictions 的建筑最大高度受左右最临近的两个restrictions 限制点限制，所以也就可以抽象为只用考虑restrictions 限制点的建筑最大高度不能超过上一个限制点的最大高度 + 两者距离和不能超过 下一个限制点的最大高度 + 两者距离,这必须经过两轮限制

现在开始求所有限制点的最大高度

如果restrictions 为空则最大高度为n-1

排序restrictions

遍历restrictions内所有数据，从左往右（最左限制点为[1,0]），求得增长限制高度与下一个restrictions 限制高度比较后取最小值，遍历完所有点

从右往左（最右限制点为[ n，restrictions[-1][1] +( n - restrictions[-1][0] )] ，可），从的增长限制高度与上一个restrictions限制高度比较后取最小值，遍历完所有点

开始求所有限制点（带第一栋和最后一栋）中最大高度

既然从右往左中所有限制条件和限制点都已经求完，可以在从右往左中直接求出最高点，减少循环

在从右往左的循环中，直接求最大高度（注意需要提前算出restrictions最尾部限制点到第n建筑的最高峰高度和在结尾补上[1,0]限制点到restrictions第一个限制点的最高峰高度）

class Solution:
    def maxBuilding(self, n: int, restrictions: list[list[int]]) -> int:
        if not restrictions:
            return n - 1
            
        # 排序
        restrictions.sort()
        m = len(restrictions)

        # 从左向右
        prev_id, prev_h = 1, 0 
        for i in range(m):
            limit = prev_h + (restrictions[i][0] - prev_id)
            if restrictions[i][1] > limit:
                restrictions[i][1] = limit
            prev_id, prev_h = restrictions[i][0], restrictions[i][1]


        ans = max( 0, restrictions[-1][1] + (n - restrictions[-1][0]))
        
        # 从右向左
        for i in range(m - 2, -1, -1):
            limit = restrictions[i+1][1] + (restrictions[i+1][0] - restrictions[i][0])
            if restrictions[i][1] > limit:
                restrictions[i][1] = limit
                
            # 直接计算它们之间的最高峰
            id1, h1 = restrictions[i]
            id2, h2 = restrictions[i+1]
            ans = max(ans, (h1 + h2 + (id2 - id1)) // 2)
            
        # [1, 0] 到第一个限制点之间的最高峰高度
        ans = max(ans, (0 + restrictions[0][1] + (restrictions[0][0] - 1)) // 2)
        
        return ans
2 Likes