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) {
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 = 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;
for(int i=2; i<N+1;i++){
if((res[i])>result){
result = res[i];
}
}

System.out.println(result);
}
``````

}

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) {
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 = 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;
for(int i=2; i<N+1;i++){
if((res[i])>result){
result = res[i];
}
}

System.out.println(result);
}
``````

}

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 , in[length(in) - 1])
if h * length(in) > max_area
max_area = h * length(in)

return max_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 , in[length(in) - 1])
if h * length(in) > max_area
max_area = h * length(in)

return max_area
``````
algorithm  data-structures  stack  dynamic-programming