Leetcode-Solutions/Maximum_Area_rectangle_Binary_matrix.py at master · Loki-4-u/Leetcode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# Maximum Area Rectangle in Binary Matrix
n=int(input())
m=int(input())
li=[]
cans=[]
for i in range(n):
    r=[]
    for j in range(m):
        k=int(input())
        r.append(k)
    li.append(r)
lis=[]
for i in range(m):
    lis.append(0)
c1=0
for i in range(n):
    for j in range(m):
        if(li[i][j]==1):
            c1=li[i][j]+lis[j]
            lis[j]=c1
        else:
            lis[j]=0
    s1=[]
    s2=[]
    ri=[]
    le=[]
    wi=[]
    ans=[]
    for z in range(m):
        a=[]
        if(len(s1)==0):
            le.append(-1)
        elif(len(s1)>0 and s1[len(s1)-1][0]<lis[z]):
            le.append(s1[len(s1)-1][1])
        elif(len(s1)>0 and s1[len(s1)-1][0]>=lis[z]):
            while(len(s1)>0 and s1[len(s1)-1][0]>=lis[z]):
                s1.pop()
            if(len(s1)==0):
                le.append(-1)
            else:
                le.append(s1[len(s1)-1][1])
        a.append(lis[z])
        a.append(z)
        s1.append(a)
    d=m-1
    while(d>=0):
        b=[]
        if(len(s2)==0):
            ri.append(m)
        elif(len(s2)>0 and s2[len(s2)-1][0]<lis[d]):
            ri.append(s2[len(s2)-1][1])
        elif(len(s2)>0 and s2[len(s2)-1][0]>=lis[d]):
            while(len(s2)>0 and s2[len(s2)-1][0]>=lis[d]):
                s2.pop()
            if(len(s2)==0):
                ri.append(m)
            else:
                ri.append(s2[len(s2)-1][1])
        b.append(lis[d])
        b.append(d)
        s2.append(b)
        d=d-1
    ri.reverse()
    for f in range(m):
        y=ri[f]-le[f]-1
        wi.append(y)
    for g in range(m):
        an=wi[g]*lis[g]
        ans.append(an)
    cans.append(max(ans))
print(max(cans))