Leetcode 1840. Maximum Building Height
Problem Explanation
In this problem, we want to build n
new buildings in a city in a line and are labeled from 1 to n. There are certain 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.
There are also 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
. The goal is to return the maximum possible height of the tallest building.
Approach
The solution to this problem involves sorting to create a consistent order of the height restrictions and iterating through the sorted restrictions to find the roof height for each building. We can use the minimum function and the data structures vectors and arrays to solve this problem.
Let's walk through an example to demonstrate the approach of the solution.
Example
Suppose we have n = 5
and restrictions = [[2,1],[4,1]]
, we want to find the maximum possible height of the tallest building.
-
First, push the first building and the last building to the restrictions list as
[[1, 0]],[[5, 4]]
and sort the list A.A = [[1,0],[2,1],[4,1],[5,4]]
. -
Now iterate through A to find the minimum height for each building:
- i=1: dist = 2-1 = 1; A[1][1] = min(1,0+1) = 1
- i=2: dist = 4-2 = 2; A[2][1] = min(1,1+2) = 1
- i=3: dist = 5-4 = 1; A[3][1] = min(4,1+1) = 2
The new A will be [[1,0],[2,1],[4,1],[5,2]]
.
-
Now iterate through A in reverse order to find the minimum height for each building:
- i=2: dist = 5-4 = 1; A[2][1] = min(1,2+1) = 1
- i=1: dist = 4-2 = 2; A[1][1] = min(1,1+2) = 1
- i=0: dist = 2-1 = 1; A[0][1] = min(0,1+1) = 0
The new A will be [[1,0],[2,1],[4,1],[5,2]]
.
-
Now iterate through the height pairs in A to find the maximum height of the tallest building:
- ans = max(0, 1 + (2-1-abs(1-0))/2) = 1
- ans = max(1, 1 + (4-2-abs(1-1))/2) = 1
- ans = max(1, 2 + (5-4-abs(2-1))/2) = 2
The maximum height of the tallest building is 2.
Solution
C++ Solution
1#include<vector>
2#include<algorithm>
3
4using namespace std;
5
6class Solution {
7 public:
8 int maxBuilding(int n, vector<vector<int>>& restrictions) {
9 vector<vector<int>> A(restrictions);
10
11 A.push_back({1, 0});
12 A.push_back({n, n - 1});
13 sort(begin(A), end(A));
14
15 // Find minimum height for each building
16 for (int i = 1; i < A.size(); ++i) {
17 int dist = A[i][0] - A[i - 1][0];
18 A[i][1] = min(A[i][1], A[i - 1][1] + dist);
19 }
20
21 // Find minimum height for each building in reverse order
22 for (int i = A.size() - 2; i >= 0; --i) {
23 int dist = A[i + 1][0] - A[i][0];
24 A[i][1] = min(A[i][1], A[i + 1][1] + dist);
25 }
26
27 int ans = 0;
28
29 // Iterate through height pairs in A to find the maximum height of the tallest building
30 for (int i = 1; i < A.size(); ++i) {
31 int l = A[i - 1][0];
32 int r = A[i][0];
33 int hL = A[i - 1][1];
34 int hR = A[i][1];
35 ans = max(ans, max(hL, hR) + (r - l - abs(hL - hR)) / 2);
36 }
37
38 return ans;
39 }
40};
Python Solution
1from typing import List
2
3class Solution:
4 def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
5 A = restrictions + [[1, 0], [n, n - 1]]
6 A.sort()
7
8 # Find minimum height for each building
9 for i in range(1, len(A)):
10 dist = A[i][0] - A[i - 1][0]
11 A[i][1] = min(A[i][1], A[i-1][1] + dist)
12
13 # Find minimum height for each building in reverse order
14 for i in range(len(A) - 2, -1, -1):
15 dist = A[i + 1][0] - A[i][0]
16 A[i][1] = min(A[i][1], A[i + 1][1] + dist)
17
18 ans = 0
19
20 # Iterate through height pairs in A to find the maximum height of the tallest building
21 for i in range(1, len(A)):
22 l, r = A[i - 1][0], A[i][0]
23 hL, hR = A[i - 1][1], A[i][1]
24 ans = max(ans, max(hL, hR) + (r - l - abs(hL - hR)) // 2)
25
26 return ans
Java Solution
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6 public int maxBuilding(int n, int[][] restrictions) {
7 List<int[]> A = new ArrayList<>(Arrays.asList(restrictions));
8 A.add(new int[]{1, 0});
9 A.add(new int[]{n, n - 1});
10 A.sort((o1, o2) -> Integer.compare(o1[0], o2[0]));
11
12 // Find minimum height for each building
13 for (int i = 1; i < A.size(); ++i) {
14 int dist = A.get(i)[0] - A.get(i - 1)[0];
15 A.get(i)[1] = Math.min(A.get(i)[1], A.get(i - 1)[1] + dist);
16 }
17
18 // Find minimum height for each building in reverse order
19 for (int i = A.size() - 2; i >= 0; --i) {
20 int dist = A.get(i + 1)[0] - A.get(i)[0];
21 A.get(i)[1] = Math.min(A.get(i)[1], A.get(i + 1)[1] + dist);
22 }
23
24 int ans = 0;
25
26 // Iterate through height pairs in A to find the maximum height of the tallest building
27 for (int i = 1; i < A.size(); ++i) {
28 int l = A.get(i - 1)[0];
29 int r = A.get(i)[0];
30 int hL = A.get(i - 1)[1];
31 int hR = A.get(i)[1];
32 ans = Math.max(ans, Math.max(hL, hR) + (r - l - Math.abs(hL - hR)) / 2);
33 }
34
35 return ans;
36 }
37}
With these solutions, you can find the maximum height of the tallest building in various programming languages, including C++, Python, and Java.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.