在直方图中,一个长方形由其左边界和右边界决定,其最大可能的高度由两者中的最小者决定。记 R(i,j) 为由第 i 个直方柱为左边界,第 j 个直方柱确定的面积最大的长方形。如果 R(i,j) 的面积最大,那么,第 i 个直方柱比它的前一个直方柱(如果存在的话),
即第 i-1 个直方柱要高,而 第 j 个直方柱的高度也比第 j+1 个的要高,否则,由 R(i,j+1) 或 R(i-1,j) 的面积比 R(i,j) 还要大,这违背了 R(i,j) 的最优性。
根据这个观察,我们从第1个直方柱开始,寻找第一个 i, 使得直方柱 i 的高度比 i+1 的大,则 i 是一个可能的右边界......
阅读全文