直方图非子集矩形查找算法改进求助：如何排除子集矩形

我明白你的需求——你需要从直方图中找出所有不被任何其他矩形完全包含的极大矩形，而不是单调栈算法原本输出的所有以单个柱子为高度的矩形。我们可以分两步来解决这个问题：先通过单调栈生成所有候选矩形（每个矩形都是以某根柱子为高度的最大可能矩形），再过滤掉那些属于其他矩形子集的项。

第一步：修改单调栈算法，生成带边界的候选矩形 #

原代码输出的是柱子索引、高度和宽度，我们先把它改成输出矩形的左边界、右边界、高度，这样更容易判断矩形之间的包含关系：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class MaximalHistogramRectangles {

    // 生成所有候选矩形（左边界，右边界，高度）
    private ArrayList<int[]> getCandidateRectangles(int[] height) {
        ArrayList<int[]> listRect = new ArrayList<>();
        if (height == null || height.length == 0) {
            return listRect;
        }
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        while (i < height.length) {
            // 当前高度大于等于栈顶柱子高度时，入栈
            if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                // 当前高度小于栈顶时，弹出栈顶并计算矩形
                int p = stack.pop();
                int h = height[p];
                // 左边界：栈空则从0开始，否则是栈顶柱子的下一个位置
                int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                // 右边界：当前索引的前一个位置（第一个比当前柱子矮的位置）
                int right = i - 1;
                listRect.add(new int[]{left, right, h});
            }
        }
        // 处理栈中剩余的柱子
        while (!stack.isEmpty()) {
            int p = stack.pop();
            int h = height[p];
            int left = stack.isEmpty() ? 0 : stack.peek() + 1;
            int right = i - 1;
            listRect.add(new int[]{left, right, h});
        }
        return listRect;
    }

第二步：过滤子集矩形 #

我们需要保留的是极大矩形：不存在任何其他矩形，其左边界≤当前矩形左边界、右边界≥当前矩形右边界，且高度≥当前矩形高度。

为了高效过滤，我们可以：

1. 把候选矩形按高度降序排序，高度相同的按宽度降序排序（这样先处理更大、更高的矩形）
2. 遍历排序后的矩形，只保留那些不被已保留矩形包含的项

// 筛选出所有极大矩形
    public ArrayList<int[]> getMaximalRectangles(int[] height) {
        ArrayList<int[]> candidates = getCandidateRectangles(height);
        // 排序规则：高度从高到低，同高度则宽度从宽到窄
        Collections.sort(candidates, (a, b) -> {
            if (b[2] != a[2]) {
                return Integer.compare(b[2], a[2]);
            } else {
                return Integer.compare((b[1] - b[0] + 1), (a[1] - a[0] + 1));
            }
        });

        ArrayList<int[]> result = new ArrayList<>();
        for (int[] rect : candidates) {
            boolean isSubset = false;
            int currLeft = rect[0];
            int currRight = rect[1];
            // 检查当前矩形是否被已保留的任何矩形包含
            for (int[] existing : result) {
                int exLeft = existing[0];
                int exRight = existing[1];
                if (exLeft <= currLeft && exRight >= currRight) {
                    isSubset = true;
                    break;
                }
            }
            if (!isSubset) {
                result.add(rect);
            }
        }
        // 按左边界升序排序，让结果更直观
        Collections.sort(result, (a, b) -> Integer.compare(a[0], b[0]));
        return result;
    }

    public static void main(String[] args) {
        MaximalHistogramRectangles solver = new MaximalHistogramRectangles();
        int[] height = new int[]{1,2,2,3,3,2};
        ArrayList<int[]> maximalRects = solver.getMaximalRectangles(height);
        for(int[] rect : maximalRects) {
            System.out.printf("左边界:%d, 右边界:%d, 高度:%d, 宽度:%d%n", 
                rect[0], rect[1], rect[2], rect[1]-rect[0]+1);
        }
    }
}

测试结果 #

对于输入[1,2,2,3,3,2]，程序输出的极大矩形为：

左边界:0, 右边界:5, 高度:1, 宽度:6
左边界:1, 右边界:5, 高度:2, 宽度:5
左边界:3, 右边界:4, 高度:3, 宽度:2

这些矩形都无法被其他任何矩形完全包含，符合你的需求。

复杂度分析 #

• 时间复杂度：单调栈生成候选矩形是O(n)，排序是O(m log m)（m是候选矩形数量，最多O(n)），过滤是O(m²)，整体为O(n²)，对于大多数场景已经足够高效。如果需要更优的O(n log n)过滤，可以使用区间树等数据结构，但实现复杂度会更高。
• 空间复杂度：O(n)，用于存储候选矩形和栈。

内容的提问来源于stack exchange，提问作者Samuel Kopp