P7.4 StoneWall
Cover "Manhattan skyline" using the minimum number of rectangles.
-
P7.4 石墙
用最少的矩形覆盖“曼哈顿天际线”
要建一面长N米的石墙。石墙墙壁笔直,厚度不变,但不同地方的高度不同。由N个正整数组成的数组H,代表石墙的不同地方的高度。H[I]表示墙从I到I+1米处的高度。特别地,H[0]是墙最左端到1米处的高度,H[N-1]是墙N-1米处到最右端的高度。
墙体应采用长方体石块(即,此类石块的所有侧面均为矩形)。目标是计算构建墙所需的最小块数。
编写函数:
def solution(H)
给定一个由N个正整数组成的数组H,指定墙的高度,则返回构建墙所需的最小块数。
例如,给定包含N=9个整数的数组H:
H[0] = 8,H[1] = 8,H[2] = 5,H[3] = 7,H[4] = 9,H[5] = 8,H[6] = 7,H[7] = 4,H[8] = 8
要建立的石墙见下图:
image下图显示了七个石块所有布局中的3种:
image因为七个石块是最小的,因此函数应返回7。
假定:
-
N是区间[1,100000]内的整数;
-
数组H的每个元素都是区间[1,100000000]内的整数;
- 解题思路
如上图,遍历高度数组,如果当前高度大于上一个高度,就添加到列表中;等于的话,就可以视为一个,不用考虑;小于的话,此处需要添加新的矩形了,就等于在这个高度上横切。前面有几个大于他的高度,就需要为这几个高度添加覆盖他们的矩形。因为已经为他们添加过矩形,所以以后就不用考虑了。 然后把当前高度添加到列表中即可。
- Python3代码
# -*- coding:utf-8 -*-
# &Author AnFany
# Lesson 7:Stacks and Queues
# P 7.4 StoneWall
def solution(H):
"""
返回构成石墙H,所需要的最小的矩形石块的个数
:param H: 代表石墙的高度数组
:return: 返回矩形石块的个数
"""
stone_count = 0
stone_list = []
for i in H:
while len(stone_list) != 0 and stone_list[-1] > i:
stone_list.pop(-1)
stone_count += 1
if len(stone_list) == 0 or i > stone_list[-1]:
stone_list.append(i)
stone_count += len(stone_list)
return stone_count
- 结果
点击获得更多编程练习题。欢迎Follow,感谢Star!!! 扫描关注微信公众号pythonfan,获取更多。
image image
网友评论