CSES - Advertisement

Solution 1

The largest rectangle must have the same height as the shortest bar that it contains. For each $i$, consider the largest rectangle with height $\text{heights}[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 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. See the stacks module for more details.

Time Complexity: $\mathcal O(N)$.

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<ll> heights(n);
	for (ll &i : heights) { cin >> i; }

Copy
n = int(input())
heights = list(map(int, input().split()))

mono_stack = []
area = [0] * n

# left to right
for i in range(n):
	while mono_stack and heights[mono_stack[-1]] >= heights[i]:
		mono_stack.pop()

Solution 2

Actually, we only need to go through the heights in one direction. When we see (i, heights[i]), we process all rectangles with right end at i-1 and height greater than heights[i]. Note how we process the rectangles that end at the last height by emptying the stack.

Time Complexity: $\mathcal O(N)$.

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<ll> heights(n);
	for (ll &i : heights) { cin >> i; }

Copy
n = int(input())
heights = list(map(int, input().split()))

ans = 0
mono_stack = []

for i in range(n):
	start = i
	while mono_stack and heights[i] < mono_stack[-1][1]:
		curr = mono_stack[-1]

Alternatively, one can add -1 to the list of heights so we don't have to treat rectangles that end at the last height in heights as a special case.

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<ll> heights(n);
	for (ll &i : heights) { cin >> i; }

Copy
n = int(input())
heights = list(map(int, input().split()))
heights.append(-1)

mono_stack = [-1]
ans = 0

for i in range(n + 1):
	while mono_stack[-1] != -1 and heights[mono_stack[-1]] >= heights[i]:
		x = mono_stack[-1]