MaximumRectangle - 最大長方形
(lib/17-rectangle/MaximumRectangle.cpp)

• View this file on GitHub
• Last update: 2023-08-19 07:15:04+09:00

MaximumRectangle

• 最大長方形
• ヒストグラムの最大長方形を求める

メソッド

• long long MaximumRectangle(vector ar)
• 計算量はarのサイズを$N$として$O(N)$

参考資料

• Flip and Rectangles

Verified with

• test/rectangle/MaximumRectangle-1.test.cpp
• test/rectangle/MaximumRectangle-2.test.cpp

Code

/*
 * @title MaximumRectangle - 最大長方形
 * @docs md/rectangle/MaximumRectangle.md
 */
long long MaximumRectangle(vector<long long> ar){
	ar.push_back(0);
	stack<pair<long long,long long>> st;
	long long res = 0;
	for(long long r = 0; r < ar.size(); ++r){
		long long vr = ar[r];
		long long x = r;		
		while(st.size() && st.top().first > vr) {
			auto [vl, l] = st.top(); st.pop();
			x = l;
			res = max(res,vl*(r - l));
		}
		if(st.empty() || (st.size() && st.top().first < vr)) st.push({vr,x});
	}
	return res;
}

#line 1 "lib/17-rectangle/MaximumRectangle.cpp"
/*
 * @title MaximumRectangle - 最大長方形
 * @docs md/rectangle/MaximumRectangle.md
 */
long long MaximumRectangle(vector<long long> ar){
	ar.push_back(0);
	stack<pair<long long,long long>> st;
	long long res = 0;
	for(long long r = 0; r < ar.size(); ++r){
		long long vr = ar[r];
		long long x = r;		
		while(st.size() && st.top().first > vr) {
			auto [vl, l] = st.top(); st.pop();
			x = l;
			res = max(res,vl*(r - l));
		}
		if(st.empty() || (st.size() && st.top().first < vr)) st.push({vr,x});
	}
	return res;
}

Back to top page