In this post, we are going to solve the Largest Rectangle in Histogram Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
Problem
Given an array of integers heights representing the histogram‘s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4] Output: 4
Constraints:
1 <= heights.length <= 1050 <= heights[i] <= 104
Now, let’s see the leetcode solution of Largest Rectangle in Histogram Leetcode Solution.
Largest Rectangle in Histogram Leetcode Solution in Python
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
ans = 0
stack = []
for i in range(len(heights) + 1):
while stack and (i == len(heights) or heights[stack[-1]] > heights[i]):
h = heights[stack.pop()]
w = i - stack[-1] - 1 if stack else i
ans = max(ans, h * w)
stack.append(i)
return ans
Largest Rectangle in Histogram Leetcode Solution in CPP
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
stack<int> stack;
for (int i = 0; i <= heights.size(); ++i) {
while (!stack.empty() &&
(i == heights.size() || heights[stack.top()] > heights[i])) {
const int h = heights[stack.top()];
stack.pop();
const int w = stack.empty() ? i : i - stack.top() - 1;
ans = max(ans, h * w);
}
stack.push(i);
}
return ans;
}
};
Largest Rectangle in Histogram Leetcode Solution in Java
class Solution {
public int largestRectangleArea(int[] heights) {
int ans = 0;
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i <= heights.length; ++i) {
while (!stack.isEmpty() && (i == heights.length || heights[stack.peek()] > heights[i])) {
final int h = heights[stack.pop()];
final int w = stack.isEmpty() ? i : i - stack.peek() - 1;
ans = Math.max(ans, h * w);
}
stack.push(i);
}
return ans;
}
}
Note: This problem Largest Rectangle in Histogram is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.
