# 資訊

:::info
- Question: 85. Maximal Rectangle
- From: Leetcode Daily Challenge 2024.04.13
- Difficulty: Hard
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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

> Example 3:
:::success
* Input: `matrix = [["1"]]`
* Output: 1
:::

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

---

# 解法

## 概念

> Ref: https://leetcode.com/problems/maximal-rectangle/solutions/4172980/stack-and-dp-unveiling-the-secrets-to-count-maximal-rectangles-full-explanation-mr-robot

計算 rectangle 面積就是長乘上寬，所以應該要有地方記錄著長寬，這邊使用 `maxAreaOfSubMatrixOfAll1` 紀錄連續 height 是多少，而 `largestRectangleArea` 則是把 width 計算出來，核心概念其實就是在這邊

不過是看 solution 得到的，好像也還沒有很懂，monotonic stack 和 DP 一起出真的滿過分的

## 程式碼

class Solution:
    def largestRectangleArea( self, heights, m ):
        stack = []
        maxArea = 0

        for i in range( m + 1 ):
            while stack and ( i == m or heights[stack[-1]] >= heights[i] ):
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                maxArea = max( maxArea, height * width )
            stack.append(i)

        return maxArea

    def maxAreaOfSubMatrixOfAll1( self, matrix, n, m ):
        maxArea = 0
        height = [0 for i in range(m) ]

        for i in range(n):
            for j in range(m):
                if matrix[i][j] == '1':
                    height[j] += 1
                else:
                    height[j] = 0
            area = self.largestRectangleArea( height, m )
            maxArea = max( maxArea, area )
        
        return maxArea

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        n, m = len( matrix ), len( matrix[0] )
        return self.maxAreaOfSubMatrixOfAll1( matrix, n, m )

---

# 複雜度

## 時間複雜度

時間跟空間差不多，因為要填完所有東西，所以是 $O(nm)$


## 空間複雜度

有 height 記錄每一格的連續 height，然後 stack 紀錄 width，height 部分占了 $O(nm)$，stack 部分也是 $O(nm)$，整體還是 $O(nm)$