All prompts are owned by LeetCode. To view the prompt, click the title link above.
First completed : June 11, 2024
Last updated : July 01, 2024
Related Topics : Array, Stack, Monotonic Stack
Acceptance Rate : 44.968 %
# Primary issue is that with this method, if the histogram is increasing only, then
# there are a LOT of checks and loops...
# Could reverse but it's a matter of knowing whether it's primarily increasing or decreasing.
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
''' This makes it work but I do think this would be cheating. It does improve
runtime for *this* version in order to make it barely satisfy the necessary runtime
and is in theory valid but again, I believe there's a better solution I need to find.
The reversal if the histogram is primarily increasing is a good way to reduce runtime since
my algorithm is optimized for a decreasing histogram, but it overall does little for a
relatively uniform case. It simply helps counteract the edge case for what I designed my
algo after.
Runtime ends up being in the 5% percentile.
'''
counter = 0
for i in range(1, len(heights)) :
if heights[i] >= heights[i - 1] :
counter += 1
if counter > len(heights) // 2 :
heights = list(reversed(heights))
prevMaxes = []
maxArea = 0
for i, height in enumerate(heights) :
lastIndx = i
while prevMaxes and prevMaxes[-1][1] >= height :
lastIndx = prevMaxes.pop()[0]
if prevMaxes and prevMaxes[-1][0] - lastIndx > height - prevMaxes[-1][1] :
continue
prevMaxes.append((lastIndx, height))
for prevMax in prevMaxes :
maxArea = max((i - prevMax[0] + 1) * prevMax[1], maxArea)
return maxArea# V2 that's *slightly* better but still not the greatest
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
prevMaxes = []
maxArea = 0
for i, height in enumerate(heights) :
lastIndx = i
while prevMaxes and prevMaxes[-1][1] > height :
maxArea = max(maxArea, (i - prevMaxes[-1][0]) * prevMaxes[-1][1])
lastIndx = prevMaxes.pop()[0]
prevMaxes.append((lastIndx, height))
maxArea = max((i - lastIndx + 1) * height, maxArea)
while prevMaxes :
maxArea = max((len(heights) - prevMaxes[-1][0]) * prevMaxes[-1][1], maxArea)
prevMaxes.pop()
return maxArea