"""
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题完全可以转化为84那一道来做，还蛮有意思的。
"""

from typing import *


class Solution:
    def largestRectangleArea(self, height: List[int]) -> int:
        height.append(0)
        height.insert(0, 0)
        height_index = [(height[i], i) for i in range(len(height))]

        left_stack, right_stack = [], []
        left_area, right_area, area = [0 for _ in range(len(height))], [0 for _ in range(len(height))], []
        for i in range(len(height)):
            cur = height_index[i]
            if len(right_stack) == 0 or cur[0] >= right_stack[-1][0]:
                right_stack.append(cur)
            else:
                while len(right_stack) > 0 and right_stack[-1][0] > cur[0]:
                    tmp = right_stack.pop()
                    right_area[tmp[1]] = tmp[0] * (cur[1] - tmp[1] - 1)
                right_stack.append(cur)

        for i in range(len(height) - 1, -1, -1):
            cur = height_index[i]
            if len(left_stack) == 0 or cur[0] >= left_stack[-1][0]:
                left_stack.append(cur)
            else:
                while len(left_stack) > 0 and left_stack[-1][0] > cur[0]:
                    tmp = left_stack.pop()
                    left_area[tmp[1]] = tmp[0] * (tmp[1] - cur[1] - 1)
                left_stack.append(cur)

        for i in range(len(height)):
            area.append(left_area[i] + right_area[i] + height[i])

        return max(area)

    def calcAxis(self, matrix: List[List[int]], row: int) -> List[int]:
        rtn = [0 for _ in range(len(matrix[0]))]
        for i in range(row):
            for j in range(len(rtn)):
                rtn[j] = rtn[j] + 1 if matrix[i][j] == '1' else 0
        return rtn

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        max_area = 0
        for row in range(1, len(matrix) + 1):
            height = self.calcAxis(matrix, row)
            tmp = self.largestRectangleArea(height)
            max_area = max_area if max_area >= tmp else tmp
        return max_area

