Given N histograms each with a width of 1 unit (as shown in the diagram below), find the maximum rectangular area that can be formed in this histogram.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| One set of test data consists of the first line containing an integer N, followed by N lines, each containing a single number H representing the height of each histogram bar. (1 <= N, H <= 10000) | Output the maximum rectangle area formed by the histograms. |
| 12 2 3 4 8 5 2 4 3 3 4 5 1 | 22 |
Thought Process
Use a Map to record occurrences of each height. Then iterate through Map using for (auto it : Map) to determine the maximum rectangle area for each height. Inside this loop, run another for loop from 0 to N-1. Outside this loop, initialize a variable count to 0. If there is a break condition, reset count to 0. Before resetting, calculate count multiplied by the current height and determine the maximum value.
Sample Code－ZeroJudge C907: Largest Rectangle
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, num[20000] = {}, ans = -999;
cin >> N;
map<int, int>MAP;
for (int i = 0; i<N; i++) {
cin >> num[i];
MAP[num[i]]++;
}
for (auto it:MAP) {
const int height = it.first;
int count = 0;
for (int i = 0; i<N; i++) {
if (num[i] < height) {
ans = max(ans, count*height);
count = 0;
continue;
}
count++;
}
ans = max(ans, count*height);
}
cout << ans << "\n";
}
//ZeroJudge C907
//Dr. SeanXD