#1840
Maximum Building Height
master · 1755 · lc hard +32 · verified · 38.4% accepted · 404 likes · top 17%
Description
You are constructing n buildings numbered 1 through n in a line. The height rules are:
- All heights must be non-negative integers.
- Building 1 must have height 0.
- Adjacent buildings may differ in height by at most 1.
Certain buildings have maximum height limits given by restrictions[i] = [idi, maxHeighti] (building 1 is never restricted).
Return the maximum height that any building can reach.
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:
Input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
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,3,4,4,5,4,3], and the tallest building has a height of 5.
Code
1
2
3