Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def largestRectangleArea(self, nums: List[int]) -> int:
- #find nearest left smallest number
- n = len(nums)
- lmin = [None]*n
- st = []
- for i in range(n):
- while st and nums[st[-1]]>=nums[i]:
- st.pop()
- if not st:
- lmin[i]= -1
- else:
- lmin[i] = st[-1]
- st.append(i)
- rmin = [None]*n
- st = []
- for i in range(n-1,-1,-1):
- while st and nums[st[-1]]>=nums[i]:
- st.pop()
- if not st:
- rmin[i] = n
- else:
- rmin[i] = st[-1]
- st.append(i)
- ans = 0
- for i in range(n):
- ans = max(ans,(rmin[i]-lmin[i]-1)*nums[i])
- return ans
Advertisement
Add Comment
Please, Sign In to add comment