arrays - 「開いた」インデックスのリストのみを調べることによって、グリッド内のすべての最大の開いた長方形のリストを見つける

Answer 1

利用可能な座標のリストがソートされます。

したがって、リストとしても、現在までの最大の長方形をグローバルに持っています。

リスト ウォークを実行し、すべての項目に対して、その項目から始まるサブリストを使用して関数を呼び出します。そのアイテムの左上から始まる最大の長方形を見つける。

public List<Coord> getMaxRectangle(List<Coord> openCoords) {
    List<Coord> currentMaxRectangle = null;
    for (int i = 0; i < openCoords.size(); ++i) {
        // Handle all rectangles starting here:
        currentMaxRectangle = maxRectangleStartingAt(i, currentMaxRectangle);
    }
    return currentMaxRectangle;
}

public List<Coord> maxRectangleStartingAt(int i, List<Coord> openCoords) {
    // Now the interesting part:
    // Take the maximal width list first: standing for all widths 1, ... max width.
    List<Coord> rect = new ArrayList<>();
    for (int j = i; j < openCoords.size()
            && openCoords.get(j).y == openCoords.get(i).y
            && openCoords.get(j).x - openCoords.get(i).x == j - i;
            ++j) {
        rect.add(openCoords.get(j);
    }
    int maxWidth = rect.size();
    // Now we can look for next lines below rect.get(0), ... get(maxWidth - 1),
    // continuously diminishing maxWidth till 0.
    // When we need to diminish maxWidth, we can look wether the original
    // maxWidth by (currentY - 1) is a maximum result.
    ...
}

だから私たちは歩きます：

           +-------------+ 1st rect
           |           |
           |           | 2nd rect
           |      | 3rd rect
           |   | 4th rect

---

O(N²) の複雑さのデモンストレーション:

public static void main(String[] args) {
    int[][] openCoords = {
        {0, 2},
        {1, 0},
        {1, 1},
        {1, 2},
        {2, 0},
        {2, 1}
    };
    new MaxRectFinder().find(openCoords);
}

private int[] maximumTopLeft;
private int[] maximumSize;

private void find(int[][] openCoords) {
    maximumTopLeft = null;
    maximumSize = new int[2];
    for (int topLeftCandidateI = 0; topLeftCandidateI < openCoords.length; ++topLeftCandidateI) {
        int yOrig = openCoords[topLeftCandidateI][0];
        int xOrig = openCoords[topLeftCandidateI][1];
        int y = yOrig;
        int x = xOrig + 1;
        int j = topLeftCandidateI + 1;
        while (j < openCoords.length
                && openCoords[j][0] == y
                && openCoords[j][1] == x) {
            ++x;
            ++j;
        }
        // Now we have a maximum x.
        for (;;) {
            // Skip after right side on current line:
            while (j < openCoords.length
                    && openCoords[j][0] == y) {
                ++j;
            }
            ++y;
            // Check for maximum:
            if (maximumTopLeft == null || (y - yOrig)*(x - xOrig) > maximumSize[0] * maximumSize[1]) {
                maximumSize[0] = y - yOrig;
                maximumSize[1] = x - xOrig;
                maximumTopLeft = openCoords[topLeftCandidateI];
            }
            // Skip before left side below origin:
            while (j < openCoords.length
                    && openCoords[j][0] == y
                    && openCoords[j][1] < x) {
                ++j;
            }
            if (j >= openCoords.length
                    || openCoords[j][0] != y
                    || openCoords[j][1] != x) {
                break;
            }
            // Register rectangle part:
            int x2 = xOrig;
            while (j < openCoords.length
                    && openCoords[j][0] == y
                    && openCoords[j][1] == x2
                    && x2 <= x) {
                ++x2;
                ++j;
            }
            x = x2;
        }
    }
    if (maximumTopLeft == null) {
        System.out.println("No solution found, not even 1x1.");
    } else {
        System.out.printf("At [%d, %d] with size [%d, %d].%n",
                maximumTopLeft[0], maximumTopLeft[1], maximumSize[0], maximumSize[1]);
    }
}