To solve this problem, we need to count the number of rectangles (including squares) in an n x n grid where all cells in the rectangle are black. The approach involves using a histogram-based method combined with a monotonic stack to efficiently count the rectangles.

Approach

1. Histogram Construction: For each row in the grid, construct a histogram where each element at position j represents the number of consecutive black cells from the current row upwards (including the current row) in column j. If the current cell is white, the value is zero.
2. Count Rectangles in Histogram: For each histogram, use a monotonic stack to count the number of rectangles. The stack helps find the first smaller element to the left and right of each bar, which allows us to determine the number of rectangles that can be formed with the current bar as the smallest bar in the rectangle.

Solution Code

def count_rectangles(grid):
    if not grid or not grid[0]:
        return 0
    n = len(grid)
    total = 0
    h = [0] * n

    for row in grid:
        # Update the histogram for current row
        for j in range(n):
            h[j] = h[j] + 1 if row[j] == 1 else 0

        # Compute the number of rectangles in the current histogram
        stack = []
        count = 0
        for i in range(n + 1):
            current_h = h[i] if i < n else 0
            while stack and h[stack[-1]] > current_h:
                height = h[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                # The number of rectangles contributed by this height
                count += height * width
            stack.append(i)
        total += count
    return total

# Example usage:
# grid = [[1,1],[1,1]]
# print(count_rectangles(grid)) # Output:6

Explanation

1. Histogram Construction: For each row, we update the histogram array h where each entry h[j] is incremented if the current cell grid[row][j] is black (1), otherwise reset to zero. This gives us the height of consecutive black cells up to the current row in each column.
2. Monotonic Stack for Histogram: The stack maintains indices of the histogram bars in non-decreasing order of their heights. For each bar, when we encounter a shorter bar, we pop the stack and calculate the number of rectangles that can be formed using the popped bar as the smallest bar. The width of these rectangles is determined by the current index and the index of the next smaller bar to the left (from the stack). The count of rectangles for this bar is the product of its height and width, which we add to the total count for the histogram.

This approach efficiently counts all valid rectangles in O(n²) time complexity, which is optimal for the given problem constraints. The use of a monotonic stack ensures that each bar is pushed and popped from the stack at most once, leading to linear time complexity for each histogram. Summing the counts from all histograms gives the total number of valid rectangles in the grid.

作者声明:本文包含人工智能生成内容。