v******s
发帖数: 51 | 1 1。 求直方图的最大内接矩形,假设每个细条的宽度为1
写了个算法，不知道对不对：
假设直方图为数组A=(a1,a2,。。。,an),ai代表第i个column的高度
################算法基于以下两个推论###################
#1最大的内接矩形，一定和直方图某一个column的上沿重合#
#2根据木桶原理，内接矩形的高度等于其包括的column中最低的#
MaxRectIndx = 0;
MaxRectArea = 0;
for i = 1:length(A)
。IndxLeft = i;
。IndxRight = i;
。while IndxLeft >= 1
。。if A(IndxLeft)>=A(i)
。。。IndxLeft = IndxLeft-1;
。。else
。。。break;
。。end
。end
。while IndxRight <= length(A)
。。if A(IndxRight)>=A(i)
。。。IndxRight = IndxRight+1;
。。else
。。。break;
。。end
。end
。temp |
|
