java - 如何递归地找到直方图中的最大矩形面积？

Question

我需要为“直方图中的最大矩形区域”问题提出一个递归解决方案。对于那些不熟悉的人，这里有一个解释:

直方图是统计信息的显示，它使用矩形来显示数据项的频率。这些矩形通常是垂直的。

在直方图中，所有条形通常具有不同的大小。在该问题中，您必须找到直方图中的最大矩形面积。例如，如果尺寸为 [4,1,4,5,6]，则最大面积为 12，因为我们采用最后 3 个条形 [4,5,6]，采用最短的条形 [4]，并应用矩形面积公式(4x3=12)。

唯一的要求是:

-它必须在java中完成。

-无法使用堆栈。

-它必须是递归的。

如果有帮助，我有一个非递归解决方案:

public static int MaxHistograma(int[] histograma) {
        if (histograma.length == 1) {
            return histograma[0];
        }
        int res = 0;
        for (int i = 0; i < histograma.length - 1; i++) {
            int min = histograma[i];
            for (int j = i + 1; j < histograma.length; j++) {
                min = Math.min(min, histograma[j]);
                res = Math.max(histograma[j], Math.max(res, min * (j - i + 1)));
                res = Math.max(res, histograma[i]);
            }
        }
        return res;
    }

Answer 1

如果您从包含 1 列的直方图的基本情况开始，则最大面积仅等于该列的高度。

当您添加包括第二列时，该区域可能是

1) 等于上一个直方图的最大面积

2) 等于第二列的高度

3)等于水平形成的新矩形的面积

当你看第三列时，它是一样的。它可以是上一个直方图的最大面积(2 列)、新列的高度(红色)或水平矩形的面积(紫色)。

这是实现此目的的代码框架

private int getLargestArea(int[] histogram)
{
    if (histogram.length > 1)
    {
        int horizontalRectangleArea = 0; //TODO
        int lastColumnHeight = 0; //TODO

        return Math.max(
            Math.max(horizontalRectangleArea, lastColumnHeight),
            getLargestArea(Arrays.copyOf(histogram, histogram.length - 1)) //copy the array, subtracting 1 column
        );
    }
    else
    {
        return histogram[0]; // height of single column
    }
}