ヒストグラム上の最大長方形 (dp/largest_histogram_rectangle.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-01 15:13:19+09:00

なにこれ

ヒストグラム上の最大矩形の面積を求める．

関数

• largest_histogram_rectangle(v)：幅 $1$ で高さ $v[i]$ のヒストグラム上に存在する最大矩形の面積を返す．

計算量

• $O(|v|)$

参考

• ヒストグラムの中の最大の長方形を見つけるアルゴリズム - Rustコトハジメ

Verified with

• test/aoj_0116.cpp
• test/aoj_DPL_3_C.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> long long largest_histogram_rectangle(vector<T> &v) {
	v.emplace_back(0);
	int n = v.size();
	long long mxrec = 0;
	stack<pair<T, int>> s;
	for(int i = 0; i < n; i++) {
		int ni = i;
		while(s.size() > 0 and s.top().first > v[i]) {
			long long h = s.top().first, w = i - s.top().second;
			long long rec = h * w;
			if(mxrec < rec) mxrec = rec;
			ni = s.top().second;
			s.pop();
		}
		s.emplace(v[i], ni);
	}
	return mxrec;
}

#line 2 "dp/largest_histogram_rectangle.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> long long largest_histogram_rectangle(vector<T> &v) {
	v.emplace_back(0);
	int n = v.size();
	long long mxrec = 0;
	stack<pair<T, int>> s;
	for(int i = 0; i < n; i++) {
		int ni = i;
		while(s.size() > 0 and s.top().first > v[i]) {
			long long h = s.top().first, w = i - s.top().second;
			long long rec = h * w;
			if(mxrec < rec) mxrec = rec;
			ni = s.top().second;
			s.pop();
		}
		s.emplace(v[i], ni);
	}
	return mxrec;
}

Back to top page