Largest Rectangle

LargestRectangle.cpp

// largestRectangle.cpp : Defines the entry point for the console application.
//

#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

vector<string> split_string(string);

class area_info {
public:
	int width;
	int height;

	area_info(int w, int h) : width(w), height(h)
	{

	}
	
	long inline area() const {
		return width * height;
	}
};

class find_bound_info {
public:
	int newHeight;
	area_info * last_info;

	find_bound_info(int height) : newHeight(height)
	{

	}
};

void visit_area(const area_info & info, long & largestArea)
{
	long area = info.area();
	if (area > largestArea)
		largestArea = area;
}

void expand_width(vector<area_info> & areas, int expand, long & largestArea)
{
	for (vector<area_info>::iterator it = areas.begin(); it != areas.end(); it++)
	{
		area_info & info = *it;
		info.width += expand;
		visit_area(info, largestArea);
	}
}

int compare_height(void const * key, void const * value)
{
	area_info * pinfo = (area_info *)value;
	find_bound_info* bound_info = (find_bound_info*)key;
	int diff = bound_info->newHeight - pinfo->height;
	if (diff <= 0)
		bound_info->last_info = pinfo;
	return diff;
}

int find_bounds(vector<area_info> & area, int newHeight)
{
	find_bound_info bound_info(newHeight);
	bsearch((void *)&bound_info, area.data(), area.size(), sizeof(area_info), compare_height);
	return bound_info.last_info - area.data ();
}

// Complete the largestRectangle function below.
long largestRectangle(vector<int> & h) {

	if (h.size() == 0)
		return 0L;

	long largestArea = 0;
	vector<area_info> areas;

	area_info current_area (0, h[0]);
	int delta = 1;

	for (size_t i = 1; i < h.size (); i++)
	{
		int newHeight = h[i];

		if (newHeight == current_area.height) {
			delta++;
			continue;
		}

		current_area.width += delta;
		expand_width(areas, delta, largestArea);
		delta = 1;
		areas.push_back(current_area);

		area_info info = area_info(0, newHeight);
		int lastHeight = current_area.height;
		current_area = info;

		if (newHeight > lastHeight)
			continue;
		
		const area_info & first = areas.front();
		if (first.height > newHeight) {
			areas.clear();
			current_area.width += i;
			continue;
		}
		
		int pos = find_bounds(areas, newHeight);
		
		const area_info & bound = areas[pos];
		int remove_count = areas.size() - pos;
		areas.erase(areas.end() - remove_count, areas.end());

		current_area.width += bound.width;
	}

	current_area.width += delta;
	expand_width(areas, delta, largestArea);
	visit_area(current_area, largestArea);

	return largestArea;
}

int main()
{
	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);

	cout << result << "\n";


	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;
}