algorithm - 算法计算可见建筑物的最小数量？

我一直在试图制定一个算法来解决一个问题。在这个问题上，我们有一张包含一些建筑物的照片照片被分成n个垂直区域（称为块），并给出了每一块中建筑物的高度。
一个建筑可以跨越多个连续的部分，但是每个部分只能包含一个可见的建筑，或者根本没有建筑。我们需要找到最少的建筑数量。
例如
鉴于，
3（件数）
1 2 3（高度）ans=3
三
1 2 1 ans=2
六
1 2 3 1 2 3 ans=5（图wud帮助显示重叠部分）。
虽然我觉得我得到了它，但我无法得到一个可靠的算法有什么想法吗？

最佳答案

您可以从给定的数组中找到最低的数字，并说明该数字的所有出现次数这将把数组分成多个子数组，现在需要递归地解决每个子数组的问题。
在示例中：

1 2 3 1 2 3 (total = 0)

最小值为1：

x 2 3 x 2 3 (total = 1)

现在你有两个子阵。
求解第一个-最小的数字是2：

  x 3       (total = 2)

最后有一个元素：total=3
求解另一个子阵使其为5。
这是C_中的一些代码：

int Solve(int[] ar, int start, int end){
    //base for the recursion -> the subarray has single element
    if(end-start == 1) return 1;

    //base for the recursion -> the subarray is empty
    if(end-start < 1) return 0;

    //find min
    int m = int.MaxValue;
    for(int i = start; i < end; i++)
        if (ar[i] < m) m = ar[i];

    int total = 1;
    //find the subarrays and their contribution recursively
    int subStart = start;
    for(int subEnd = start; subEnd < end; subEnd++){
        if(ar[subEnd] == m) {
            total += Solve(ar, subStart, subEnd);
            subStart = subEnd + 1;
        }
    }
    total += Solve(ar, subStart, ar.Length);

    return total;
}