Compute the largest rectangle under the skyline
LargestRectangleUnderSkyline.javapublic static int calculateLargestRectangleAlternative(List<Integer> A) {
// Calculate L.
LinkedList<Integer> s = new LinkedList<>();
List<Integer> L = new ArrayList<>();
for (int i = 0; i < A.size(); ++i) {
while (!s.isEmpty() && A.get(s.peek()) >= A.get(i)) {
s.pop();
}
L.add(s.isEmpty() ? -1 : s.peek());
s.push(i);
}
// Clear stack for calculating R.
while (!s.isEmpty()) {
s.pop();
}
int[] R = new int[A.size()];
for (int i = A.size() - 1; i >= 0; --i) {
while (!s.isEmpty() && A.get(s.peek()) >= A.get(i)) {
s.pop();
}
R[i] = s.isEmpty() ? A.size() : s.peek();
s.push(i);
}
// For each A[i], find its maximum area include it.
int maxArea = 0;
for (int i = 0; i < A.size(); ++i) {
maxArea = Math.max(maxArea, A.get(i) * (R[i] - L.get(i) - 1));
}
return maxArea;
}
Largest_rectangle_under_skyline.h
int calculate_largest_rectangle_alternative(const vector<int>& A) {
// Calculate L.
stack<int> s;
vector<int> L;
for (int i = 0; i < A.size(); ++i) {
while (!s.empty() && A[s.top()] >= A[i]) {
s.pop();
}
L.emplace_back(s.empty() ? -1 : s.top());
s.emplace(i);
}
// Clear stack for calculating R.
while (!s.empty()) {
s.pop();
}
vector<int> R(A.size());
for (int i = A.size() - 1; i >= 0; --i) {
while (!s.empty() && A[s.top()] >= A[i]) {
s.pop();
}
R[i] = s.empty() ? A.size() : s.top();
s.emplace(i);
}
// For each A[i], find its maximum area include it.
int max_area = 0;
for (int i = 0; i < A.size(); ++i) {
max_area = max(max_area, A[i] * (R[i] - L[i] - 1));
}
return max_area;
}
// @include
int calculate_largest_rectangle(const vector<int>& A) {
stack<int> s;
int max_area = 0;
for (int i = 0; i <= A.size(); ++i) {
while (!s.empty() && (i == A.size() || A[i] < A[s.top()])) {
int height = A[s.top()];
s.pop();
max_area = max(max_area, height * (s.empty() ? i : i - s.top() - 1));
}
s.emplace(i);
}
return max_area;
}
