Leetcode 84. Largest Rectangle in Histogram
Problem Explanation:
We are given heights of bars in a Histogram and we are asked to find the largest rectangle in this histogram. The task is to maximize the area of the rectangle formed. There are two parameters that define this area: the height and width of the rectangle. Height will be the smallest height among the histogram bars under consideration (for the rectangle), and width will be range of the continuous bars.
For example, consider the following histogram where width of each bar is 1 and the given heights are [2,1,5,6,2,3].
1 2 3 | | 4 | | | 5 | | | | 6 | | | | 7__|_|_|_|__ 8 9 2,1,5,6,2,3
The largest rectangle in this histogram is formed by the bars of height 5 and 6. It has an area of 10 units (height 5 * width 2).
Solution Approach:
The solution uses stack data structure as well as iterating through the heights. Each element of the heights array is treated as potential minimum height of the largest rectangle. When we reach a height smaller than the previous one while iterating, we have found a potential maximum rectangle (with the bar at top of the stack being the smallest).
We pop elements from the stack continuously until we find a height smaller or equal to the current one, and for each popped bar, we calculate area of rectangle with the popped bar height as smallest bar. we calculate the area and update the maximum area if current rectangle area is more.
This approach works because the stack always holds the bars with heights in increasing order from bottom to up. Once the stack is empty, we start a new rectangle with the current bar. This way we are guaranteed to not miss any possible largest rectangle.
Python Solution:
1 2python 3class Solution: 4 def largestRectangleArea(self, heights: List[int]) -> int: 5 maxarea = 0 6 stack = [-1] 7 for i in range(len(heights)): 8 while stack[-1] != -1 and heights[stack[-1]] >= heights[i]: 9 maxarea = max(maxarea, heights[stack.pop()] * (i - stack[-1] - 1)) 10 stack.append(i) 11 12 while stack[-1] != -1: 13 maxarea = max(maxarea, heights[stack.pop()] * (len(heights) - stack[-1] - 1)) 14 15 return maxarea
Java Solution:
1 2java 3class Solution { 4 public int largestRectangleArea(int[] heights) { 5 Stack <Integer> s = new Stack<>(); 6 int max_area=0; 7 int tp; 8 int area_with_top; 9 int i=0; 10 while(i<heights.length){ 11 if(s.empty() || heights[s.peek()]<=heights[i]) s.push(i++); 12 else { 13 tp= s.peek(); 14 s.pop(); 15 area_with_top=heights[tp]*(s.empty()? i:i-s.peek()-1); 16 if(max_area<area_with_top) max_area=area_with_top; 17 } 18 } 19 while(s.empty()==false){ 20 tp=s.peek(); 21 s.pop(); 22 area_with_top=heights[tp]*(s.empty()? i:i-s.peek()-1); 23 if(max_area<area_with_top) max_area=area_with_top; 24 } 25 return max_area; 26 } 27}
JavaScript Solution:
1 2javascript 3var largestRectangleArea = function(heights) { 4 let maxArea = 0; 5 const stack = []; 6 heights.push(0); 7 8 for (let i = 0; i < heights.length; i++) { 9 while (stack.length && heights[i] < heights[stack[stack.length - 1]]) { 10 const height = heights[stack.pop()]; 11 const width = stack.length ? i - stack[stack.length - 1] - 1 : i; 12 maxArea = Math.max(maxArea, width * height); 13 } 14 stack.push(i); 15 } 16 return maxArea; 17};
C++ Solution:
1 2c++ 3class Solution { 4public: 5 int largestRectangleArea(vector<int>& heights) { 6 stack<int> s; 7 heights.push_back(0); 8 int result = 0; 9 for(int i = 0; i < heights.size(); ) { 10 if(s.empty() || heights[i] > heights[s.top()]) { 11 s.push(i++); 12 } else { 13 int tmp = s.top(); 14 s.pop(); 15 result = max(result, heights[tmp] * (s.empty() ? i : i - s.top() - 1)); 16 } 17 } 18 return result; 19 } 20};
C# Solution:
1 2csharp 3public class Solution { 4 public int LargestRectangleArea(int[] heights) { 5 int maxArea = 0; 6 Stack<int> stack = new Stack<int>(); 7 for (int i = 0; i <= heights.Length; i++) { 8 int h = (i == heights.Length ? 0 : heights[i]); 9 if (stack.Count == 0 || h >= heights[stack.Peek()]) { 10 stack.Push(i); 11 } else { 12 int tp = stack.Pop(); 13 maxArea = Math.Max(maxArea, heights[tp] * (stack.Count == 0 ? i : i - 1 - stack.Peek())); 14 i--; 15 } 16 } 17 return maxArea; 18 } 19}
Key learning and considerations:
This problem serves as a good demonstration of how stacks can be effectively utilized to solve problems involving histograms or similar height-based data. By retaining a 'stack' of potential histograms to examine, we can easily backtrack to investigate other possible rectangles when we encounter a lower height. This approach prevents the need for excessive computation or the storage of every potential rectangle.
These implementations in Python, Java, JavaScript, C++, and C# all share some common features. They all use a stack to keep track of indexes of the bars in the histograms. They start from the first bar, and every time we go to a new bar, we compare it with the top of the stack, and if it's smaller, then we know we've reached the end of a potential rectangle and we can calculate the area.
The solutions also add a zero height bar at the end of the heights list to ensure that all the bars in the stack are popped out, which would be reflected in the final maximum area result.
Each language has its own unique traits and syntax for handling this kind of problem, but the underlying algorithm remains the same. Python's solution is quite clean and concise, using Python's list as a stack. Java's Stack object provides handy methods like .peek() and .empty(). JavaScript's function-style solution uses a very similar approach to Python with array serving as a stack. The C++ solution uses a vector and stack with very clear and explicit steps. C# solution, similar to Java, uses a Stack object with .peek() and .count properties.
Understanding these similarities and contrasts can aid you in becoming more adept in the language of your choice and in expanding your comprehension of data structures and problem-solving strategies.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.