> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0085-maximal-rectangle.md).

# 0085. Maximal Rectangle

<https://leetcode.com/problems/maximal-rectangle>

## Description

Given a `rows x cols` binary `matrix` filled with `0`'s and `1`'s, find the largest rectangle containing only `1`'s and return *its area*.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/09/14/maximal.jpg)

```
**Input:** matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
**Output:** 6
**Explanation:** The maximal rectangle is shown in the above picture.
```

**Example 2:**

```
**Input:** matrix = []
**Output:** 0
```

**Example 3:**

```
**Input:** matrix = [["0"]]
**Output:** 0
```

**Example 4:**

```
**Input:** matrix = [["1"]]
**Output:** 1
```

**Example 5:**

```
**Input:** matrix = [["0","0"]]
**Output:** 0
```

**Constraints:**

* `rows == matrix.length`
* `cols == matrix[i].length`
* `0 <= row, cols <= 200`
* `matrix[i][j]` is `'0'` or `'1'`.

## ac1: Stack

similar with #84

```java
class Solution {
    public int maximalRectangle(char[][] matrix) {
        // edge cases
        if (matrix.length == 0 || matrix[0].length == 0) return 0;

        int max = 0;
        int row = matrix.length, col = matrix[0].length;
        int[] h = new int[col];
        // iterate row
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                h[c] = matrix[r][c] == '1' ? h[c] + 1 : 0;
            }
            max = Math.max(max, maxArea(h)); // O(n)
        }

        return max;
    }
    private int maxArea(int[] h) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(-1);
        int max = 0;
        for (int i = 0; i <= h.length; i++) {
            int currh = i == h.length ? 0 : h[i];
            while (stack.peek() != -1 && currh < h[stack.peek()]) {
                max = Math.max(max, h[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return max;
    }
}
/*
stack, similar with #84
row by row: int[] h = new int[matrix[0].length]
    if [i] == 1, h[i] = h[i] + 1, otherwise h[i] = 0
    calculate max area like #84
*/
```