在直方图中找到所有的矩形

Question

我相信大多数人都听说过直方图中最大矩形问题。 -链接-

在我的当前项目中，我需要更改该算法以便在直方图中找到所有不属于另一个矩形较小子集的矩形。

目前我已经做到了这一步，但我无法想出如何不计算此处的子集。

   //time: O(n), space:O(n)
     public ArrayList<int[]> largestRectangles(int[] height) {
            ArrayList<int[]> listRect = new ArrayList<int[]>();

            if (height == null || height.length == 0) {
                return null;
            }

            Stack<Integer> stack = new Stack<Integer>();

            int max = 0;
            int i = 0;

            while (i < height.length) {
                //push index to stack when the current height is larger than the previous one
                if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
                    stack.push(i);
                    i++;
                } else {
                //add rectangle when the current height is less than the previous one
                    int p = stack.pop();
                    int h = height[p];
                    int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                    listRect.add(new int[]{p,h,w});
                }

            }

            while (!stack.isEmpty()) {
                int p = stack.pop();
                int h = height[p];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                listRect.add(new int[]{p,h,w});
            }

            return listRect;
        }
public static void main(String[] args) {

         for(int[] rect : largestRectangles(new int[]{1,2,2,3,3,2})) {
             System.out.print("pos:"+rect[0]+" height"+rect[1]+" 
         width"+rect[2]);
             System.out.println();
         }
     }

- Samuel Kopp

---

我实际上没有听说过那个问题。您能否编辑您的问题，包括以下信息：什么是“直方图中最大的矩形问题”？它只是找到最高的矩形吗？如果两个或更多的矩形是最高的并且具有相同的高度，它会怎么做？一个矩形“不是另一个矩形的较小子集”是什么意思？ - Keara

我添加了一个描述的链接 :) - Samuel Kopp

太好了，谢谢！现在更清楚了。 - Keara

请澄清“矩形不是另一个矩形的较小子集”这是什么意思。附图可能有帮助。 - c0der

Answer 1

这个想法是检查新添加的矩形是否包含上一个添加的矩形；如果是，则在将此新矩形添加到结果列表之前（通过高度确认），从结果列表中删除上一个添加的矩形信息。我手头没有Java IDE，所以尝试了C#。

以下是需要在两个地方添加的部分（请转换为Java），就在listRect.Add(new[] {p,h,w}.)之前。

if (listRect.Count > 0)
{

    if (listRect[listRect.Count - 1][1] <= h)
    {
        listRect.RemoveAt(listRect.Count - 1);
    }
}

这只是一个想法。您需要编写逻辑来省略其中值为0的直方图的删除逻辑，例如new int[] { 1, 2, 2, 3, 3, 2, 0, 1 }等。但逻辑相似；您需要存储标志等，并根据其位置绕过最后一个矩形的删除。

- sbp