# Share my Python solution using RMQ

• The idea is based on the article on geeksforgeeks. I made changes for the method to find the maximum rectangular area. The original is a recursive function, which will reach maximum stack depth for Python. So I've changed it into an iterative one. Time complexity is O(NlogN).

``````import math

class Solution(object):
def largestRectangleArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
def _RMQHelper(height, segment_tree, start, end, query_start, query_end, node_index):
'''
helper function to get the index of minimum value in a given range of indice.
height:                 List[int],  the input list for which segment tree is built
segment_tree:           List[int],  the segment tree
start, end:             int,        starting / ending indice of segment represented by current node, segment_tree[node_index]
query_start, query_end: int,        starting and ending indice of query range
index:                  int,        index of current node in the segment tree. root is always at index 0
'''
if (query_start <= start) and (query_end >= end):
# segment of this node is part of query range, return the minimum of the segment
return segment_tree[node_index]
if (query_start > end) or (query_end < start):
# segment of this node is outside the query range
return -1

# part of this segment overlaps with the query range, check left and right part recursively
middle = (start + end) >> 1
left  = _RMQHelper(height, segment_tree, start, middle, query_start, query_end, (node_index<<1) + 1)
right = _RMQHelper(height, segment_tree, middle+1, end, query_start, query_end, (node_index<<1) + 2)
if left == -1:
return right
elif right == -1:
return left
return left if height[left] < height[right] else right

# range minimum query to get index of minimum element in range [query_start, query_end]
def _RMQ(height, segment_tree, query_start, query_end):
return _RMQHelper(height, segment_tree, 0, len(height)-1, query_start, query_end, 0)

# find the maximum rectangular area in range [query_start, query_end]
def _getMaxAreaHelper(height, segment_tree, query_start, query_end):
stack, max_area = [(query_start, query_end)], 0
# need to use stack to avoid stack depth overflow
while stack:
query_start, query_end = stack.pop()
if query_start == query_end:
# only one bar in the range
if height[query_start] > max_area:
max_area = height[query_start]
else:
# get the index of lowest bar in the given range
min_index = _RMQ(height, segment_tree, query_start, query_end)
# calculate rectangle area including the lowest bar
area = (query_end - query_start + 1) * height[min_index]
if area > max_area:
max_area = area
# push end-points of left and right halves onto stack
if query_start < min_index:
stack.append((query_start, min_index - 1))
if query_end > min_index:
stack.append((min_index + 1, query_end))
return max_area

length = len(height)
if length > 0:
# Build segment tree from height
segment_tree = self.constructST(height)
return _getMaxAreaHelper(height, segment_tree, 0, length-1)
else:
return 0

# construct segment tree
def constructST(self, height):
# helper
def _constructSTHelper(height, segment_tree, start, end, node_index):
if start == end:
# If there is only one element in array, store it in the current node
segment_tree[node_index] = start
else:
# recursively scan left and right subtrees and store the minimum of the two values in this node
middle = (start + end) >> 1
left  = _constructSTHelper(height, segment_tree, start, middle, (node_index<<1) + 1)
right = _constructSTHelper(height, segment_tree, middle+1, end, (node_index<<1) + 2)
segment_tree[node_index] = left if height[left] < height[right] else right

return segment_tree[node_index]

# build segment tree
length = len(height)
segment_tree = [0] * (2**(int(math.ceil(math.log(length, 2))) + 1) - 1)
_constructSTHelper(height, segment_tree, 0, length-1, 0)
return segment_tree
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.