fork(1) download
  1. def largest_rectangle(hs):
  2. stack = []
  3. i = m = 0
  4.  
  5. while i < len(hs) or stack:
  6. if i == len(hs) or (stack and hs[stack[-1]] > hs[i]):
  7. h = hs[stack.pop()]
  8. s = 0 if not stack else stack[-1] + 1
  9. x = min(h, i - s)
  10. m = max(m, x * x)
  11. continue
  12. stack.append(i)
  13. i += 1
  14. return m
  15.  
  16. inp = """X--X-
  17. -----
  18. -----
  19. -----
  20. ---X-"""
  21.  
  22. grid = list(map(list, inp.split('\n')))
  23. r = [0 for _ in grid[0]]
  24. largest = 0
  25. for row in grid:
  26. r = [(1 + h) if el == '-' else 0 for h, el in zip(r, row)]
  27. largest = max(largest, largest_rectangle(r))
  28.  
  29. print(largest)
  30.  
Success #stdin #stdout 0.02s 9936KB
stdin
Standard input is empty
stdout
9