最大矩形面积 --漫漫算法路 刷题篇
输入描述:
输入包括两行,第一行包含一个整数n(1 ≤ n ≤ 10000) 第二行包括n个整数,表示h数组中的每个值,h_i(1 ≤ h_i ≤ 1,000,000)
输出描述:
输出一个整数,表示最大的矩阵面积。
输入例子1:
6 2 1 5 6 2 3解法一:直接循环遍历 两次循环 从第一个开始 依次与和后面的组成新的部分,取最大值 最后进行比较
import java.util.Scanner;
public class Main{public static int getArea(int[] num){
if(num.length==1)
return 0;
if(num.length==2)
return num[1];
int len = num.length-1;
int minHeight=0,area=0;
for(int m=1;m<=len;m++){
minHeight = num[m];
for(int n=m+1;n<=len;n++){
minHeight = Math.min(minHeight,num[n]);
if(height[j]>area ){
area = height[j];
}
}
}
return area;
}
public static void main(String arg[]){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[] num = new int[n+1];
for(int i=1;i<=n;i++){
num[i] = sc.nextInt();
}
int area = getArea(num);
System.out.print(area+"");
}
}
}
解法二:只循环一次,遍历所有数字 每次找到其两边连续的不小于它的数 得到宽度 求出最大值
import java.util.Scanner;
public class Main{
public static long getArea(int[] num){
if(num.length==1)
return 0;
if(num.length==2)
return num[1];
int len = num.length-1;
long temarea=0,area=0;
for(int m=1;m<=len;m++){
/* minHeight = num[m];
for(int n=m+1;n<=len;n++){
minHeight = Math.min(minHeight,num[n]);
area = Math.max(area,(n-m+1)*minHeight);
}*/
int left =m,right =m;
while(left>1&&num[left-1]>=num[m]){
left--;
}
while(right<len&&num[right+1]>=num[m]){
right++;
}
temarea =(right-left+1)*num[m];
if(temarea>area){
area = temarea;
}
}
return area;
}
public static void main(String arg[]){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[] num = new int[n+1];
for(int i=1;i<=n;i++){
num[i] = sc.nextInt();
}
long area = getArea(num);
System.out.print(area+"");
}
}
}