Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #One pass soln
- class Solution:
- def largestRectangleArea(self, heights: List[int]) -> int:
- res = 0
- heights.append(-1)
- st = [-1]
- for i, x in enumerate(heights):
- while x < heights[st[-1]]:
- res = max(res, heights[st.pop()]*(i-st[-1]-1))
- st.append(i)
- return res
- #multiple pass soln
- class Solution:
- def largestRectangleArea(self, heights: List[int]) -> int:
- n = len(heights)
- #previous smallest element problem
- st = []
- prevs = [-1]*n
- for i, e in enumerate(heights):
- while st and heights[st[-1]] >= e:
- st.pop()
- if st:
- prevs[i] = st[-1]
- st.append(i)
- #next smallest element problem
- st.clear()
- nxts = [n]*n
- for i, e in enumerate(heights):
- while st and heights[st[-1]] >= e:
- nxts[st.pop()] = i
- st.append(i)
- res = 0
- for i,x in enumerate(heights):
- res = max(res, (nxts[i]-prevs[i]-1)*x)
- return res
Add Comment
Please, Sign In to add comment