You want to build n
new buildings in a city. The new buildings will be built in a line and are labeled from 1
to n
.
However, there are city restrictions on the heights of the new buildings:
- The height of each building must be a non-negative integer.
- The height of the first building must be
0
. - The height difference between any two adjacent buildings cannot exceed
1
.
Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array restrictions
where restrictions[i] = [idi, maxHeighti]
indicates that building idi
must have a height less than or equal to maxHeighti
.
It is guaranteed that each building will appear at most once in restrictions
, and building 1
will not be in restrictions
.
Return the maximum possible height of the tallest building.
Example 1:
Input: n = 5, restrictions = [[2,1],[4,1]] Output: 2 Explanation: The green area in the image indicates the maximum allowed height for each building. We can build the buildings with heights [0,1,2,1,2], and the tallest building has a height of 2.
Example 2:
Input: n = 6, restrictions = [] Output: 5 Explanation: The green area in the image indicates the maximum allowed height for each building. We can build the buildings with heights [0,1,2,3,4,5], and the tallest building has a height of 5.
Example 3:
1 2 3 4 |
<strong>Input:</strong> n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]] <strong>Output:</strong> 5 <strong>Explanation:</strong> The green area in the image indicates the maximum allowed height for each building. We can build the buildings with heights [0,1,2,3,3,4,4,5,4,3], and the tallest building has a height of 5. |
Constraints:
2 <= n <= 109
0 <= restrictions.length <= min(n - 1, 105)
2 <= idi <= n
idi
is unique.0 <= maxHeighti <= 109
Solution: Two Passes
Trim the max heights based on neighboring max heights.
Two passes: left to right, right to left.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: int maxBuilding(int n, vector<vector<int>>& rs) { rs.push_back({1, 0}); sort(begin(rs), end(rs)); if (rs.back()[0] != n) rs.push_back({n, n - 1}); const int m = rs.size(); for (int i = 1; i < m; ++i) rs[i][1] = min(rs[i][1], rs[i - 1][1] + rs[i][0] - rs[i - 1][0]); for (int i = m - 2; i >= 0; --i) rs[i][1] = min(rs[i][1], rs[i + 1][1] - rs[i][0] + rs[i + 1][0]); int ans = 0; for (int i = 1; i < m; ++i) { const int l = rs[i - 1][1]; const int r = rs[i][1]; ans = max(ans, max(l, r) + (rs[i][0] - rs[i - 1][0] - abs(l - r)) / 2); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment