Codility 7.4 Stone Wall [stack a

Cover "Manhattan skyline" using the minimum number of rectangles.

Task description

You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is specified by an array H of N positive integers. H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular, H[0] is the height of the wall's left end and H[N−1] is the height of the wall's right end.

The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular). Your task is to compute the minimum number of blocks needed to build the wall.

Write a function:
given an array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it.

For example, given array H containing N = 9 integers:
the function should return 7. The figure shows one possible arrangement of seven blocks.

![image](https://img.haomeiwen.com/i3593554/b30c412be2fec36d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

Write an ****efficient**** algorithm for the following assumptions:

> *   N is an integer within the range [1..100,000];
> *   each element of array H is an integer within the range [1..1,000,000,000].

H =[8,8,5,7,9,8,7,4,8]
这个可以用贪心算法，如下图。
就拿这个list H来说，前两个8，一块石头，5到7，一块石头，7到7，一块石头，9到8，一块石头，9，一块石头，4和8，一块石头，8，一块石头，总共7块。

solution2

这个算法的重点是看下一个高度是不是比当前高度大，如果H[i+1]>H[i]，那他们还能共用一块石头，如果小于，那就从头再来，横着切一刀分割出来一个矩形。
具体做法是：

1. 遍历数组，如果墙的当前高度比stack的最后一个还大，那就写入当前高度。
2. 当前高度比stack小，那就pop，再写入当前高度。如果当前高度一直比stack小，那就一直Pop,直到找到新的起点。
3. 相等的话stack不做改动，相邻的元素不能相同，因为相同就可以看做一块，没必要再加入stack了。
4. stack里的元素有变动，那么stones就加一
5. stack用来存递增序列。

solution

def solution(H):
    # write your code in Python 3.6
    stack = []
    num = 0
    for i in range(len(H)):
        while len(stack)>0 and stack[-1]>H[i]:
            stack.pop()
        if len(stack)==0 or stack[-1]<H[i]:
            stack.append(H[i])
            num +=1
        elif stack[-1]==H[i]:
            continue
    return num
            

Official solution