Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Largest Rectangle in Histogram

Posted on January 26, 2018July 26, 2020 by braindenny

Largest Rectangle in Histogram



Similar Problems:

  • LeetCode: Maximal Rectangle
  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: monotone, #rectangle

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Largest Rectangle in Histogram
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

Largest Rectangle in Histogram

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/largest-rectangle-in-histogram
## Basic Ideas: Monotone stack
##              For each element, find the next non-greater value
##     Key Questions: How to get the left?
##                    What if right is not found, any special logic?
##
## Complexity:
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        length = len(heights)
        next_smallers = [-1] * length
        stack = []
        max_width = 0
        # pad with fake items for the end
        for i in xrange(length+1):
            current = heights[i] if i != length else -1
            # When heights[i] is not greater than the stack top, it's the target of stack top
            while len(stack) != 0 and  current <= heights[stack[-1]]:
                k = stack.pop()
                h = heights[k]
                left = -1 if len(stack) == 0 else stack[-1]
                left = left + 1
                right = i
                max_width = max(max_width, h*(right-left))
            stack.append(i)
        return max_width

# s = Solution()
# print s.largestRectangleArea([2, 1, 2]) # 3
linkedin
github
slack

Post Views: 9
Posted in HardTagged #inspiring, monotone, rectangle

Post navigation

LeetCode: Maximal Square
LeetCode: Basic Calculator III

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.