Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# liyunrui/84. Largest Rectangle in Histogram.py

Created Feb 15, 2021
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
to join this conversation on GitHub. Already have an account? Sign in to comment