找到你要的答案

Q:Can anybody please tell me what is wrong with my code?

Q:谁能告诉我代码有什么问题?

Problem Statement: There are N buildings in a certain one-dimensional landscape. Each building has a height given by hi,i∈[1,N]. If you join K adjacent buildings, they will form a solid rectangle of area K×min(hi,hi+1,…,hi+k−1).

Given N buildings, find the greatest such solid area formed by consecutive buildings.

Below is my solution. It looks fine to me but it is failing for test cases. Can anybody please tell me what is wrong with below solution.

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);
}

}

问题陈述:在一定的一维景观中存在N个建筑物。每个建筑都有高度的你好,我∈[ 1,]。如果你加入K邻近建筑物,它们将形成一个坚实的矩形区域K×min(嗨,嗨,嗨,+ + 1,…−1 K)。

给定n个建筑物,找出连续建筑物形成的最大固体面积。

Below is my solution. It looks fine to me but it is failing for test cases. Can anybody please tell me what is wrong with below solution.

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);
}

}

answer1: 回答1:

There are way faster solutions than brute-force, by simply mapping each building to it's counterpiece like this:

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

Now it's pretty simple to find the maximum-area:

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

有更快的解决方案比蛮力,通过简单的映射每个建筑它的counterpiece这样:

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

现在找到最大的区域很简单:

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  data-structures  stack  dynamic-programming