algorithm - 给定N座建筑物，找出由连续建筑物形成的最大此类实体区域

问题陈述：在某个一维景观中有N个建筑每栋楼的高度由hi，i∈[1，N]给出如果将K个相邻建筑连接起来，它们将形成一个面积K×min（hi，hi+1，…，hi+K-1）的实心矩形。
给定n个建筑物，找出由连续建筑物形成的最大实体面积。
下面是我的解决方案在我看来很好，但是对于测试用例来说它是失败的。
有谁能告诉我下面的解决方案有什么问题吗。

public class Solution {

    public static void main(String[] args) {
        InputReader ir = new InputReader(System.in);
        int N = ir.nextInt();
        long [] hts = new long[N];
        long [] res = new long[N+1];
        for(int i=0; i<N; i++){
            hts[i] = ir.nextLong();
        }

        //Computes max area for subset of length 1
        long max = Integer.MIN_VALUE;
        for(int i=1; i<=N; i++){
            if(max<hts[i-1]){
                 max = hts[i-1];
            }
        }

        res[1] = max;
        /* Computes max of all the minimum heights
         * of subsets of length i and
         * store area at res[i] position
         */
        for(int i=2; i<=N; i++){
            max = Integer.MIN_VALUE;
            for(int j=0; j<N-i+1; j++){
                long min = hts[j];
                for(int k=j+1;k<i-j;k++){
                    if(hts[k]<min){
                        min = hts[k];
                    }
                }
                if(min>max){
                    max = min;
                }
            }
            res[i] = i*max;
        }

       // Get maximum area
        long result = res[1];
        for(int i=2; i<N+1;i++){
            if((res[i])>result){
                result = res[i];
            }
        }

        System.out.println(result);
    }
}

最佳答案

有比暴力更快的解决方案，只需将每栋建筑映射到其对应物上，如下所示：

           _____
      _____|   |
______|<--||-->|_____
|<---||---||---||-->|
|    ||   ||   ||   |

现在很容易找到最大面积：

int getMaxArea(int[] in)
    map height_to_maxw

    stack last_height
    stack at_pos

    int max_area = 0

    for int i in [0 , length(in))
        if !last_heigth.isEmpty()
            while last_height.peek() > in[i]
                int l_h = last_height.pop()
                int l_w = i - at_pos.pop()

                if l_h * l_w > max_area
                    max_area = l_h * l_w

    //check if the widest area is the greatest
    int h = min(in[0] , in[length(in) - 1])
    if h * length(in) > max_area
        max_area = h * length(in)

    return max_area

关于algorithm - 给定N座建筑物，找出由连续建筑物形成的最大此类实体区域，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33020176/