maximum-building-height

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You want to build <code>n</code> new buildings in a city. The new buildings will be built in a line and are labeled from <code>1</code> to <code>n</code>.

However, there are city restrictions on the heights of the new buildings:

<ul>
	<li>The height of each building must be a non-negative integer.</li>
	<li>The height of the first building must be <code>0</code>.</li>
	<li>The height difference between any two adjacent buildings cannot exceed <code>1</code>.</li>
</ul>

Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array <code>restrictions</code> where <code>restrictions[i] = [idi, maxHeighti]</code> indicates that building <code>idi</code> must have a height less than or equal to <code>maxHeighti</code>.

It is guaranteed that each building will appear at most once in <code>restrictions</code>, and building <code>1</code> will not be in <code>restrictions</code>.

Return the maximum possible height of the tallest building.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex1-1.png" style="width: 400px; height: 253px;" />
<pre>
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.</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex2.png" style="width: 500px; height: 269px;" />
<pre>
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.
</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex3.png" style="width: 500px; height: 187px;" />
<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 109</code></li>
	<li><code>0 &lt;= restrictions.length &lt;= min(n - 1, 105)</code></li>
	<li><code>2 &lt;= idi &lt;= n</code></li>
	<li><code>idi</code>&nbsp;is unique.</li>
	<li><code>0 &lt;= maxHeighti &lt;= 109</code></li>
</ul>

maxBuilding

Maximum Building Height

Array

Math

Sorting

在一座城市里，你需要建 <code>n</code> 栋新的建筑。这些新的建筑会从 <code>1</code> 到 <code>n</code> 编号排成一列。

这座城市对这些新建筑有一些规定：

<ul>
	<li>每栋建筑的高度必须是一个非负整数。</li>
	<li>第一栋建筑的高度 必须 是 <code>0</code> 。</li>
	<li>任意两栋相邻建筑的高度差 不能超过  <code>1</code> 。</li>
</ul>

除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 <code>restrictions</code> 的形式给出，其中 <code>restrictions[i] = [idi, maxHeighti]</code> ，表示建筑 <code>idi</code> 的高度 不能超过 <code>maxHeighti</code> 。

题目保证每栋建筑在 <code>restrictions</code> 中 至多出现一次 ，同时建筑 <code>1</code> 不会 出现在 <code>restrictions</code> 中。

请你返回 最高 建筑能达到的 最高高度 。

 

示例 1：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/25/ic236-q4-ex1-1.png" style="width: 400px; height: 253px;" />
<pre>
输入：n = 5, restrictions = [[2,1],[4,1]]
输出：2
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,1,2] ，最高建筑的高度为 2 。</pre>

示例 2：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/25/ic236-q4-ex2.png" style="width: 500px; height: 269px;" />
<pre>
输入：n = 6, restrictions = []
输出：5
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,3,4,5] ，最高建筑的高度为 5 。
</pre>

示例 3：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/25/ic236-q4-ex3.png" style="width: 500px; height: 187px;" />
<pre>
输入：n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
输出：5
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,3,3,4,4,5,4,3] ，最高建筑的高度为 5 。
</pre>

 

提示：

<ul>
	<li><code>2 <= n <= 109</code></li>
	<li><code>0 <= restrictions.length <= min(n - 1, 105)</code></li>
	<li><code>2 <= idi <= n</code></li>
	<li><code>idi</code> 是 唯一的 。</li>
	<li><code>0 <= maxHeighti <= 109</code></li>
</ul>