C++ Library for Competitive Programming
#include "emthrm/dynamic_programming/largest_rectangle.hpp"
$O(N)$
名前 | 戻り値 |
---|---|
template <typename T> long long largest_rectangle(const std::vector<T>& height);
|
高さ $\mathrm{height}$ で表されるヒストグラム中の長方形の最大面積 |
https://onlinejudge.u-aizu.ac.jp/solutions/problem/DPL_3_C/review/4082202/emthrm/C++14
#ifndef EMTHRM_DYNAMIC_PROGRAMMING_LARGEST_RECTANGLE_HPP_
#define EMTHRM_DYNAMIC_PROGRAMMING_LARGEST_RECTANGLE_HPP_
#include <algorithm>
#include <stack>
#include <vector>
namespace emthrm {
template <typename T>
long long largest_rectangle(const std::vector<T>& height) {
const int n = height.size();
std::vector<int> left(n);
std::stack<T> st;
long long res = 0;
for (int i = 0; i < n; ++i) {
while (!st.empty() && height[st.top()] >= height[i]) {
res = std::max(
res, static_cast<long long>(height[st.top()]) * (i - left[st.top()]));
st.pop();
}
left[i] = (st.empty() ? 0 : st.top() + 1);
st.emplace(i);
}
while (!st.empty()) {
res = std::max(
res, static_cast<long long>(height[st.top()]) * (n - left[st.top()]));
st.pop();
}
return res;
}
} // namespace emthrm
#endif // EMTHRM_DYNAMIC_PROGRAMMING_LARGEST_RECTANGLE_HPP_
#line 1 "include/emthrm/dynamic_programming/largest_rectangle.hpp"
#include <algorithm>
#include <stack>
#include <vector>
namespace emthrm {
template <typename T>
long long largest_rectangle(const std::vector<T>& height) {
const int n = height.size();
std::vector<int> left(n);
std::stack<T> st;
long long res = 0;
for (int i = 0; i < n; ++i) {
while (!st.empty() && height[st.top()] >= height[i]) {
res = std::max(
res, static_cast<long long>(height[st.top()]) * (i - left[st.top()]));
st.pop();
}
left[i] = (st.empty() ? 0 : st.top() + 1);
st.emplace(i);
}
while (!st.empty()) {
res = std::max(
res, static_cast<long long>(height[st.top()]) * (n - left[st.top()]));
st.pop();
}
return res;
}
} // namespace emthrm