Share my Python solution using RMQ


  • 0
    D

    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
    

Log in to reply
 

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