# 85. Maximal Rectangle

#### Hard

***

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 = [["0"]]
Output: 0
```

**Example 3:**

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

 

**Constraints:**

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

```python
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        for i in range(len(matrix[0])):
            matrix[0][i] = int(matrix[0][i])
        for i in range(1, len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == "0":
                    matrix[i][j] = 0
                elif matrix[i][j] != "0":
                    matrix[i][j] = int(matrix[i][j]) + int(matrix[i-1][j])
        result = 0
        for index in range(len(matrix)):
            # print(matrix[index])
            result = max(result, self.max_histogram_rectangle(matrix[index]))
        return result
    
    def max_histogram_rectangle(self, height):
        height.append(0)
        stack = [-1]
        result = 0
        for index in range(len(height)):
            while height[index] < height[stack[-1]]:
                h = height[stack.pop()]
                w = index-1 - stack[-1]
                result = max(result, h*w)
            stack.append(index)
        return result
```