直方图内最大矩阵 直方图内最大矩阵
题目描述
有一个直方图，用一个整数数组表示，其中每列的宽度为1，求所给直方图包含的最大矩形面积。比如，对于直方图[2,7,9,4],它所包含的最大矩形的面积为14(即[7,9]包涵的7x2的矩形)。
给定一个直方图A及它的总宽度n，请返回最大矩形面积。保证直方图宽度小于等于500。保证结果在int范围内。
测试样例：
[2,7,9,4,1],5
返回：14
知道怎么枚举，dp也出来了
牛客网题解：
求直方图矩形面积的最大值就是求数组中相邻元素（单个元素，两两相邻，三三相邻。。。
）中最小值乘以他们的数量得到面积，再取最大值，通过分析可以发现实际第一个元素比较一次，第二个元素比较两次，第三个元素比较三次。。。以此类推就可，对于A[n]只需记录A[n-1]之前最大面积的即可，所以不需要设置额外的数组，只需设置两个int变量即可求出面积最大值。
1 import java.util.*; 2 3 public class MaxInnerRec { 4 public int countArea(int[] A, int n) { 5 int maxArea=0; 6 int min; 7 for(int i=0;i<n;i++){ 8 min=Integer.MAX_VALUE; 9 for(int j=i;j>=0;j--){ 10 min=Math.min(min, A[j]); 11 maxArea=Math.max(maxArea,(i-j+1)*min); 12 } 13 } 14 return maxArea; 15 } 16 }
3 4 int i,j,L1,L2; 5 int max=0; 6 for(i=0;i<n;i++) 7 { 8 L1=0;L2=0; 9 for(j=i;j<n;j++) 10 { 11 if(A[j]>=A[i])L1++; 12 else break; 13 14 } 15 for(j=i-1;j>=0;--j) 16 { 17 if(A[j]>=A[i])L2++; 18 else break; 19 } 20 area=(L1+L2)*A[i]; 21 if(area>max)max=area; 22 } 23 //printf("max area:%d ",max); 24 return max;