mono stack I maximal rectangle

    def maximalhistogram(self, height):
        mono_stack, global_max, local_max = [], 0, 0
        for idx in range(len(height)):
            while len(mono_stack) > 0 and height[idx] < height[mono_stack[-1]]:
                high = height[mono_stack[-1]]
                local_max = 0
                if len(mono_stack) == 1:
                    local_max = idx * high
                else:
                    width = mono_stack[-1] - mono_stack[-2] + idx - mono_stack[-1] - 1
                    local_max = width * high
                global_max = max(global_max, local_max)
                mono_stack.pop()
            mono_stack.append(idx)
            
        while len(mono_stack) > 0:
            if len(mono_stack) > 1:
                width = len(height) - mono_stack[-1] + mono_stack[-1] - mono_stack[-2] - 1
                global_max = max(global_max, height[mono_stack[-1]] * width)
            else:
                global_max = max(global_max, height[mono_stack[-1]] * len(height))
            mono_stack.pop()
        
        return global_max
        
    def maximalRectangle(self, matrix):
        # write your code here
        if len(matrix) < 1 or len(matrix[0]) < 1:
            return 0
        max_solution, col_consecutive_row_tag = [0 for i in range(len(matrix))], [-1 for i in range(len(matrix[0]))]
        for row_id in range(len(matrix)):
            height = [0 for i in range(len(matrix[row_id]))]
            for col_id in range(len(matrix[row_id])):
                if matrix[row_id][col_id] == 1 and col_consecutive_row_tag[col_id] != -1:
                    height[col_id] = row_id - col_consecutive_row_tag[col_id] + 1
                elif matrix[row_id][col_id] == 1 and col_consecutive_row_tag[col_id] == -1:
                    col_consecutive_row_tag[col_id] = row_id
                    height[col_id] = 1
                elif matrix[row_id][col_id] == 0 and col_consecutive_row_tag[col_id] != -1:
                    col_consecutive_row_tag[col_id] = -1
            max_solution[row_id] = max(max_solution[row_id-1], self.maximalhistogram(height))
        return max_solution[-1]