企业官网建设流程全解析

Problem: 1840. 最高建筑高度

不会做，看的官方题解的，仅作为记录

数学题，贪心

Code

class Solution { public: int maxBuilding(int n, vector<vector<int>>& restrictions) { int m, mx = 0; restrictions.push_back({1, 0}); sort(restrictions.begin(), restrictions.end()); if(restrictions.back()[0] != n) restrictions.push_back({n, n - 1}); m = restrictions.size(); auto&& r = restrictions; // 从左向右传递限制 for (int i = 1; i < m; ++i) { r[i][1] = min(r[i][1], r[i - 1][1] + (r[i][0] - r[i - 1][0])); } // 从右向左传递限制 for (int i = m - 2; i >= 0; --i) { r[i][1] = min(r[i][1], r[i + 1][1] + (r[i + 1][0] - r[i][0])); } int ans = 0; for (int i = 0; i < m - 1; ++i) { // 计算 r[i][0] 和 r[i][1] 之间的建筑的最大高度 int best = ((r[i + 1][0] - r[i][0]) + r[i][1] + r[i + 1][1]) / 2; ans = max(ans, best); } return ans; } };