java - 查找直方图中的所有矩形

Question

我相信你们中的大多数人都听说过直方图问题中的最大矩形。 - Link -

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

这是我目前的进度。但我不知道如何不计算这里的子集。

   //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();
         }
     }

Answer 1

想法是检查添加的新矩形是否包含最后添加的矩形；如果是这样，那么在添加这个新信息之前，只需从结果列表中删除最后添加的矩形信息(通过高度确认)。我没有方便的 Java IDE，所以在 C# 中尝试。

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

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 } 等。但逻辑是相似的；您必须存储一个标志等，并根据其位置绕过最后一个矩形的删除。