class Stack:
    def __init__(self, data=[]):
        self.data = data

    def __repr__(self) -> str:
        return f"{self.data}"

    def peek(self):
        if self.data:
            return self.data[-1]
        else:
            return None

    def pop(self):
        return self.data.pop()

    def push(self, d):
        self.data.append(d)

    def isempty(self):
        if len(self.data) == 0:
            return True
        else:
            return False


def merge(base, addition):
    merged = []
    for i, b in enumerate(base):
        if b == 0:
            merged.append(0)
        else:
            merged.append(b + addition[i])

    return merged


def max_mat_rect(m):
    h = len(m)
    area = 0
    for i in range(h):
        hist = m[i] if i == 0 else merge(m[i], hist)
        area = max(area, max_rect(hist))
    return area


def max_rect(bars):
    stack = Stack()
    bars.append(0)
    area = 0

    for i, h in enumerate(bars):
        if stack.isempty() or h > bars[stack.peek()]:
            stack.push(i)
        else:
            while not stack.isempty() and h < bars[stack.peek()]:
                i0 = stack.pop()
                width = i - i0
                area = max(area, bars[i0] * width)

    return area


print(max_rect([0, 2, 1, 5, 5, 2, 3]))

print(max_rect([2, 4, 4]))

m = [[0, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 0, 0]]
print(max_mat_rect(m))


class Stack:
    def __init__(self, data=[]):
        self.data = data

    def __repr__(self) -> str:
        return f"{self.data}"

    def peek(self):
        if self.data:
            return self.data[-1]
        else:
            return None

    def pop(self):
        return self.data.pop()

    def push(self, d):
        self.data.append(d)

    def isempty(self):
        if len(self.data) == 0:
            return True
        else:
            return False


def merge(base, addition):
    merged = []
    for i, b in enumerate(base):
        if b == 0:
            merged.append(0)
        else:
            merged.append(b + addition[i])

    return merged


def max_mat_rect(m):
    h = len(m)
    area = 0
    for i in range(h):
        hist = m[i] if i == 0 else merge(m[i], hist)
        area = max(area, max_rect(hist))
    return area


def max_rect(bars):
    stack = Stack()
    bars.append(0)
    area = 0

    for i, h in enumerate(bars):
        if stack.isempty() or h > bars[stack.peek()]:
            stack.push(i)
        else:
            while not stack.isempty() and h < bars[stack.peek()]:
                i0 = stack.pop()
                width = i - i0
                area = max(area, bars[i0] * width)

    return area


print(max_rect([0, 2, 1, 5, 5, 2, 3]))

print(max_rect([2, 4, 4]))

m = [[0, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 0, 0]]
print(max_mat_rect(m))

