Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-stack
class Solution:
"""
Thought Process
Brute Force:
Two pointers:
T: O(n^2)
S: O(1)
Stack:
we use stack to maintain the minimum height on the left side of heights[i].
And, the top of stack is closest index of minimum height.
step1:We traverset the given height:
If current height, heights[i], <= top of stack:
we calulate the area of rectangel formed using the height of top of stack.
to make sure top e top of stack is closest index of minimum height
width = i - stack[-1], wehre i is current index but in order to handle 0-index. intially, we put -1 in the stack.
step2:掃完heights之後如果stack不為空, 我們需要去掃右半邊可能的max arre
因為當前右邊的高度一定比top of stack還高
"""
def largestRectangleArea(self, heights: List[int]) -> int:
"""
Two pointers
T: O(n^2)
S: O(1)
"""
n = len(heights)
max_area = 0
for i in range(n):
min_height = float("inf")
for j in range(i, n):
min_height = min(min_height, heights[j])
max_area = max(max_area, min_height* (j-i+1))
return max_area
def largestRectangleArea(self, heights: List[int]) -> int:
"""
Stack
T:O(n) because each index were push and pop at most once.
S:O(n)
"""
n = len(heights)
stack = collections.deque([-1])
max_area = 0
for i in range(n):
# think about case in decreasing order, then we know we need to append (-1) intially
while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
min_height_ix = stack.pop()
cur_min_height = heights[min_height_ix]
cur_width = i-1-stack[-1] # 1-1-(-1) = 1
max_area = max(max_area, cur_min_height * cur_width)
stack.append(i)
# think about case in increasing order
while stack[-1] != -1:
min_height_ix = stack.pop()
cur_min_height = heights[min_height_ix]
cur_width = len(heights)-stack[-1] - 1
max_area = max(max_area, cur_min_height * cur_width)
return max_area
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment