84. Largest Rectangle in Histogram
refer to notes please
- The largest rectangle must have the same height as the shortest bar that it contains.
- For each i, consider the largest rectangle with height H[i] such that bar i is the shortest bar it contains.
- The answer is simply the largest of these N rectangles.
- Since the heights of these rectangles are fixed, we just want them to be as wide as possible.
- Notice how the rectangle of bar $i$ is bounded by the closest shorter bars on each side of bar
i.
- (or the ends of the histogram if these bars don’t exist).
- We can use a monotone stack twice to find the closest shorter bars on each side of each bar.
also refer to notes
implementation
```cpp
class Solution {
public:
int largestRectangleArea(vector& arr) {
int n = arr.size();
stack temp, st;
vector previous_less(n), next_less(n);
for (int i = 0; i < arr.size(); i++) {
previous_less[i] = -1;
next_less[i] = arr.size();
}
// for previous less
for (int i = 0; i < n; i++) {
while (!st.empty() && arr[st.top()] >= arr[i])
st.pop();
previous_less[i] = st.empty() ? -1 : st.top();
st.push(i);
}
std::swap(temp, st);
// for next less
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && arr[st.top()] >= arr[i])
st.pop();
next_less[i] = st.empty() ? n : st.top();
st.push(i);
}
int ans = 0;
for (int i = 0; i < arr.size(); i++)
ans = max(ans, (next_less[i] - previous_less[i] - 1) * arr[i]);
return ans;
}
};
```
implementation
```cpp
class Solution {
public:
int largestRectangleArea(vector& heights) {
int n = heights.size();
stack st;
vector ans(n, 0);
for (int i = 0; i < n; i++) {
while (!st.empty() and heights[st.top()] >= heights[i])
st.pop();
int width = i - (st.empty() ? -1 : st.top());
ans[i] = width * heights[i];
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() and heights[st.top()] >= heights[i])
st.pop();
int width = (st.empty() ? n : st.top()) - 1 - i;
ans[i] += width * heights[i];
st.push(i);
}
return *max_element(ans.begin(), ans.end());
}
};
```