Codility每周一课：L7 Stacks and Queue

7.png

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。

假定：

1. N是区间[1，100000]内的整数；

2. 数组H的每个元素都是区间[1，100000000]内的整数；

• 解题思路

image

如上图，遍历高度数组，如果当前高度大于上一个高度，就添加到列表中；等于的话，就可以视为一个，不用考虑；小于的话，此处需要添加新的矩形了，就等于在这个高度上横切。前面有几个大于他的高度，就需要为这几个高度添加覆盖他们的矩形。因为已经为他们添加过矩形，所以以后就不用考虑了。 然后把当前高度添加到列表中即可。

• 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

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image