Question: https://oj.leetcode.com/problems/largest-rectangle-in-histogram/
Question name: Largest Rectangle in Histogram
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | class Solution: class Status(object): ''' A class to store the intermediate status of the dividing zone. A name tuple is better if it is allowed. ''' __slots__ = ["heightIndex", "begin", "end"] def __init__(self, heightIndex, begin, end): self.heightIndex = heightIndex self.begin = begin self.end = end return # @param height, a list of integer # @return an integer def largestRectangleArea(self, height): height = sorted(enumerate(height), key = lambda x: x[1]) # All bars have non-negative height. Area is at least 0. maxArea = 0 # Initialize the stack. Recursive solution will lead to stack overflow stack = [self.Status(0, 0, len(height)-1)] while len(stack) != 0: subSection = stack.pop() # Terminate case if subSection.begin > subSection.end: continue # Skip the bars if they are not in current zone [begin, end]. while not subSection.begin <= height[subSection.heightIndex][0] <= subSection.end: subSection.heightIndex += 1 # Liebig's law of the minimum. The height of the rectangle # is determined by the lowest bar. area = (subSection.end - subSection.begin + 1) * height[subSection.heightIndex][1] maxArea = max(maxArea, area) # All the bars in current zone [begin, end] have the same height. # No lower bar, so no need to divide current zone. if height[subSection.heightIndex][1] == height[-1][1]: continue # Divide current zone with the lowest bar. Only after removing # the lowest bar, the height of new zones could be higher # (also possibly keep the same). # # Left part of current zone. stack.append(self.Status(subSection.heightIndex+1, subSection.begin, height[subSection.heightIndex][0]-1)) # Right part of current zone. stack.append(self.Status(subSection.heightIndex+1, height[subSection.heightIndex][0]+1, subSection.end)) return maxArea |
Update on 2014-06-24: Thanks to optimization, the previous solution passed all the tests. But when I met with the question “Maximal Rectangle”, I realized the previous one is not the designed solution. After Google, the following O(N) algorithm is found.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | class Solution: # @param height, a list of integer # @return an integer def largestRectangleArea(self, height): stack = [] # Store the position of bars with non-decreasing height maxArea = 0 height.append(-1) # Append a pseudo bar at the end so that, after # the while loop, the one and the only on bar # left in the stack will definitely be this # pseudo bar. index = 0 # In this loop, we are using the stack to find out the largest zone # for each bar (to say i), in which bar i is the shortest one. while index < len(height): if len(stack) == 0: # This is the first bar. OR all of its previous bars are # higher than this one. stack.append(index) index += 1 elif height[index] >= height[stack[-1]]: stack.append(index) index += 1 else: preBasin = stack.pop() if len(stack) == 0: # From beginning to index-1 position, the preBasin has # the shortest bar. maxArea = max(maxArea, height[preBasin] * index) else: # From stack[-1] position to index-1 position, the # preBasin has the shortest bar. maxArea = max(maxArea, height[preBasin] * (index-stack[-1]-1) ) return maxArea |
Update on 2014-09-29: By chance, a shorter solution is found.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution: # @param height, a list of integer # @return an integer def largestRectangleArea(self, height): if len(height) == 0: return 0 stack = [-1] # Store the position of bars with non-decreasing height maxArea = 0 height.append(-1) # Append a pseudo bar at the end so that, after # the while loop, the one and the only on bar # left in the stack will definitely be this # pseudo bar. index = 0 # In this loop, we are using the stack to find out the largest zone # for each bar (to say i), in which bar i is the shortest one. while index < len(height): if height[index] >= height[stack[-1]]: stack.append(index) index += 1 else: preBasin = stack.pop() # From stack[-1] position to index-1 position, the # preBasin has the shortest bar. maxArea = max(maxArea, height[preBasin] * (index-stack[-1]-1) ) return maxArea |