Prompt
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.
Examples
-
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
Solution
In C++
// left to right, how many bars away
// is the next element that is less
// than the one at the current index?
vector<int> getltr(const vector<int>& heights) {
size_t n = heights.size();
vector<int> answer(n, 0);
stack<size_t> istack;
for (const auto& [i, height] : views::enumerate(heights)) {
while(!istack.empty()
&& height < heights[istack.top()]) {
size_t j = istack.top();
istack.pop();
answer[j] = i - j;
}
istack.push(i);
}
while(!istack.empty()) {
size_t j = istack.top();
istack.pop();
answer[j] = n - j;
}
return answer;
}
// right to left, how many bars away
// is the next element that is less
// than the one at the current index?
vector<int> getrtl(const vector<int>& heights) {
vector<int> rv_heights(heights);
reverse(rv_heights.begin(), rv_heights.end());
vector<int> answer = getltr(rv_heights);
reverse(answer.begin(), answer.end());
return answer;
}
int largestRectangleArea(vector<int>& heights) {
size_t n = heights.size();
vector<int> ltr = getltr(heights);
vector<int> rtl = getrtl(heights);
int max_val = 0;
for (size_t i = 0; i < heights.size(); ++i) {
int ltr_product = heights[i] * ltr[i];
int rtl_product = heights[i] * rtl[i];
int ov = ltr_product + rtl_product - heights[i];
max_val = max({max_val, ltr_product, rtl_product, ov});
}
return max_val;
}Explanation
As you will see below in Example Testcases, we transform the input array in a couple different ways, and then find the maximum of those images. We use a Monotonically Increasing Stack like in 739. Daily Temperatures to find the first occurence of a smaller bar height for each bar, both from left to right and right to left. We also consider the union between these areas.
Example Testcases
2 1 5 6 2 3 <- A: input
1 5 2 1 2 1 <- B: ltr
1 2 1 1 3 1 <- C: rtl
2 5 10 6 4 3 <- D: A * B
2 2 5 6 6 3 <- E: A * C
2 6 10 6 8 3 <- F: D union E
2 4 <- A: input
2 1 <- B: ltr
1 1 <- C: rtl
4 4 <- D: A * B
2 4 <- E: A * C
4 4 <- F: D union E
2 1 2 <- A: input
1 2 1 <- B: ltr
1 2 1 <- C: rtl
2 2 2 <- D: A * B
2 2 2 <- E: A * C
2 3 2 <- F: D union E
3 6 5 7 4 8 1 0 <- A: input
6 1 2 1 2 1 1 1 <- B: ltr
1 1 2 1 4 1 7 8 <- C: rtl
18 6 10 7 8 8 1 0 <- D: A * B
3 6 10 7 16 8 7 0 <- E: A * C
18 6 15 7 20 8 7 0 <- F: D union E - A
Big O Analysis
Time Complexity