贪心
数组
排序
堆(优先队列)
题目描述
一条完全笔直的街道由一条数字线表示。街道上有建筑物,由二维整数阵列 buildings
表示,其中 buildings[i] = [starti , endi , heighti ]
。这意味着在 半封闭的位置 [starti,endi)
有一座高度为 heighti
的建筑。
你想用 最少 数量的非重叠 部分 来 描述 街道上建筑物的高度。街道可以用2D整数数组 street
来表示,其中 street[j] = [leftj , rightj , averagej ]
描述了道路的 半封闭区域 [leftj , rightj )
,该段中建筑物的 平均 高度为 averagej
。
例如,如果 buildings = [[1,5,2],[3,10,4]]
, street = [[1,3,2],[3,5,3],[5,10,4]]
可以表示街道,因为:
从 1 到 3 ,只有第一栋建筑的平均高度为 2 / 1 = 2
。
从 3 到 5 ,第一和第二栋建筑的平均高度均为 (2+4) / 2 = 3
。
从 5 到 10 ,只有第二栋建筑的平均高度为 4 / 1 = 4
。
给定 buildings
,返回如上所述的二维整数矩阵 street
( 不包括 街道上没有建筑物的任何区域)。您可以按 任何顺序 返回数组。
n
个元素的 平均值 是 n
个元素除以 n
的 总和 (整数除法 )。
半闭合段 [a, b)
是点 a
和 b
之间的数字线的截面,包括 点 a
,不包括 点 b
。
示例1:
输入: buildings = [[1,4,2],[3,9,4]]
输出: [[1,3,2],[3,4,3],[4,9,4]]
解释:
从 1 到 3 ,只有第一栋建筑的平均高度为 2 / 1 = 2。
从 3 到 4 ,第一和第二栋建筑的平均高度均为(2+4)/ 2 = 3。
从 4 到 9 ,只有第二栋建筑的平均高度为 4 / 1 = 4。
示例 2:
输入: buildings = [[1,3,2],[2,5,3],[2,8,3]]
输出: [[1,3,2],[3,8,3]]
解释:
从 1 到 2 ,只有第一栋建筑的平均高度为 2 / 1 = 2。
从 2 到 3 ,这三座建筑的平均高度均为 (2+3+3) / 3 = 2。
从 3 到 5 ,第二和第三栋楼都在那里,平均高度为 (3+3) / 2 = 3。
从 5 到 8 ,只有最后一栋建筑的平均高度为 3 / 1 = 3。
从 1 到 3 的平均高度是相同的,所以我们可以把它们分成一个部分。
从 3 到 8 的平均高度是相同的,所以我们可以把它们分成一个部分。
示例 3:
输入: buildings = [[1,2,1],[5,6,1]]
输出: [[1,2,1],[5,6,1]]
解释:
从 1 到 2 ,只有第一栋建筑的平均高度为 1 / 1 = 1。
从 2 到 5 ,没有建筑物,因此不包括在输出中。
从 5 到 6 ,只有第二栋建筑的平均高度为 1 / 1 = 1。
我们无法将这些部分组合在一起,因为没有建筑的空白空间将这些部分隔开。
提示:
1 <= buildings.length <= 105
buildings[i].length == 3
0 <= starti < endi <= 108
1 <= heighti <= 105
解法
方法一:差分有序哈希表
我们利用差分思想,使用有序哈希表 height
记录每个位置的高度变化,cnt
记录建筑物的数量变化。对有序哈希表求前缀和,即可得到每个位置的高度和建筑物数量。
最后遍历有序哈希表,对于每个位置,如果高度和建筑物数量都不为 0,则说明该位置有建筑物,判断此时的建筑物是否与上个建筑物的平均高度相同,如果相同,则合并,否则加入结果集。
时间复杂度 $O(n \times \log n)$,空间复杂度 $O(n)$。其中 $n$ 为建筑物数量。
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution :
def averageHeightOfBuildings ( self , buildings : List [ List [ int ]]) -> List [ List [ int ]]:
height = defaultdict ( int )
cnt = defaultdict ( int )
for s , e , h in buildings :
cnt [ s ] += 1
cnt [ e ] -= 1
height [ s ] += h
height [ e ] -= h
ans = []
i = h = n = 0
for j in sorted ( cnt . keys ()):
if n :
t = [ i , j , h // n ]
if ans and ans [ - 1 ][ 1 ] == i and ans [ - 1 ][ 2 ] == t [ - 1 ]:
ans [ - 1 ][ 1 ] = j
else :
ans . append ( t )
i = j
h += height [ j ]
n += cnt [ j ]
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 class Solution {
public int [][] averageHeightOfBuildings ( int [][] buildings ) {
TreeMap < Integer , Integer > height = new TreeMap <> ();
TreeMap < Integer , Integer > cnt = new TreeMap <> ();
for ( var v : buildings ) {
int s = v [ 0 ] , e = v [ 1 ] , h = v [ 2 ] ;
cnt . put ( s , cnt . getOrDefault ( s , 0 ) + 1 );
cnt . put ( e , cnt . getOrDefault ( e , 0 ) - 1 );
height . put ( s , height . getOrDefault ( s , 0 ) + h );
height . put ( e , height . getOrDefault ( e , 0 ) - h );
}
int i = 0 , h = 0 , n = 0 ;
List < int []> res = new ArrayList <> ();
for ( int j : cnt . keySet ()) {
if ( n > 0 ) {
int [] t = new int [] { i , j , h / n };
int k = res . size () - 1 ;
if ( k >= 0 && res . get ( k ) [ 1 ] == i && res . get ( k ) [ 2 ] == t [ 2 ] ) {
res . get ( k ) [ 1 ] = j ;
} else {
res . add ( t );
}
}
h += height . get ( j );
n += cnt . get ( j );
i = j ;
}
int [][] ans = new int [ res . size () ][ 3 ] ;
for ( i = 0 ; i < ans . length ; ++ i ) {
ans [ i ] = res . get ( i );
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 class Solution {
public :
vector < vector < int >> averageHeightOfBuildings ( vector < vector < int >>& buildings ) {
map < int , int > height , cnt ;
for ( auto & v : buildings ) {
int s = v [ 0 ], e = v [ 1 ], h = v [ 2 ];
cnt [ s ] ++ , cnt [ e ] -- ;
height [ s ] += h , height [ e ] -= h ;
}
vector < vector < int >> ans ;
int i = 0 , h = 0 , n = 0 ;
for ( auto & [ j , _ ] : cnt ) {
if ( n ) {
vector < int > t = { i , j , h / n };
if ( ans . size () && ans . back ()[ 1 ] == i && ans . back ()[ 2 ] == t [ 2 ]) {
ans . back ()[ 1 ] = j ;
} else {
ans . push_back ( t );
}
}
i = j ;
h += height [ j ];
n += cnt [ j ];
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 func averageHeightOfBuildings ( buildings [][] int ) [][] int {
height := make ( map [ int ] int )
cnt := make ( map [ int ] int )
for _ , v := range buildings {
s , e , h := v [ 0 ], v [ 1 ], v [ 2 ]
cnt [ s ] ++
cnt [ e ] --
height [ s ] += h
height [ e ] -= h
}
keys := make ([] int , len ( cnt ))
for k := range cnt {
keys = append ( keys , k )
}
sort . Ints ( keys )
i , h , n := 0 , 0 , 0
ans := [][] int {}
for _ , j := range keys {
if n > 0 {
t := [] int { i , j , h / n }
if len ( ans ) > 0 && ans [ len ( ans ) - 1 ][ 1 ] == i && ans [ len ( ans ) - 1 ][ 2 ] == t [ 2 ] {
ans [ len ( ans ) - 1 ][ 1 ] = j
} else {
ans = append ( ans , t )
}
}
i = j
h += height [ j ]
n += cnt [ j ]
}
return ans
}
GitHub