Record each possible starting position(When the height increases compared with the previous height)
If the height decreases, replace the height of all the previous possible starting positions with higher height with the height at the latest position. After the replacement, the ones with equal height should be merged to have a uniform starting position.
The above process is equivalent to push the height and index of the possible starting position when there’s no element in the stacks or the new coming element is higher. Meanwhile, when the new coming height is lower, pop all the previous ones that are higher, and without changing the index of the first higher position, just replace the height of it with the new element.
When each replacement happens as well as when there are no more buildings but the stacks are still not empty, we should calculate the area before each pop operation. If the new area is larger than the current maximum, update it.
#include <bits/stdc++.h>
using namespace std;
vector<string> split_string(string);
// Complete the largestRectangle function below.
long largestRectangle(vector<int> h) {
stack<int> hStack, pStack;
int maximum = 0;
for(int i = 0; i < h.size(); ++i) {
if(hStack.empty() || h[i] > hStack.top()) {
hStack.push(h[i]);
pStack.push(i);
} else if(h[i] < hStack.top()) {
int last_p = 0;
while(!hStack.empty() && h[i] < hStack.top()) {
int area = hStack.top() * (i - pStack.top());
if(area > maximum) maximum = area;
last_p = pStack.top();
pStack.pop();
hStack.pop();
}
pStack.push(last_p);
hStack.push(h[i]);
}
}
while(!hStack.empty())
{
int area = hStack.top() * (h.size() - pStack.top());
if(area > maximum) maximum = area;
hStack.pop();
pStack.pop();
}
return maximum;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
int n;
cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), '\n');
string h_temp_temp;
getline(cin, h_temp_temp);
vector<string> h_temp = split_string(h_temp_temp);
vector<int> h(n);
for (int i = 0; i < n; i++) {
int h_item = stoi(h_temp[i]);
h[i] = h_item;
}
long result = largestRectangle(h);
fout << result << "\n";
fout.close();
return 0;
}
vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});
input_string.erase(new_end, input_string.end());
while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}
vector<string> splits;
char delimiter = ' ';
size_t i = 0;
size_t pos = input_string.find(delimiter);
while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));
i = pos + 1;
pos = input_string.find(delimiter, i);
}
splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
return splits;
}
