最大長方形問題
(algorithm/Others/largest_rectangle.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Others/largest_rectangle.hpp"

概要

「あるヒストグラム内において，面積が最大となる長方形を求める問題」を効率的に求めるテクニックアルゴリズム．

問題の概要は次の通り．

長さ $N$ の数列 $H = \lbrace h_0, h_1, \ldots, h_{N-1} \rbrace$ が与えられる．

各 $i \ (0 \leq i < N)$ において，$h_i \leq h_j$ となる $i$ を含む $j$ の最大区間を $[l,r)$ とする．

このとき $\max(h_i * (r-l))$ を求めよ．

計算量は，愚直に求めると $\mathcal{O}(N^2)$ となるが，スタックを用いて工夫すると $\mathcal{O}(N)$ に落とすことができる．

参考文献

1. 秋葉 拓哉, 岩田 陽一, 北川 宜稔. “4-4 厳選！ 頻出テクニック (2)”. プログラミングコンテストチャレンジブック. 第2版, マイナビ出版, 2012, p.298.

Verified with

• verify/aoj-DPL_3_B-largest_rectangle.test.cpp
• verify/aoj-DPL_3_C-largest_rectangle.test.cpp

Code

#ifndef ALGORITHM_LARGEST_RECTANGLE_HPP
#define ALGORITHM_LARGEST_RECTANGLE_HPP 1

/**
 * @brief 最大長方形問題
 * @docs docs/Others/largest_rectangle.md
 */

#include <functional>
#include <stack>
#include <utility>
#include <vector>

namespace algorithm {

// 最大長方形問題．
// 各iにおいて，comp(H[i], H[] within [l,r))==true となるiを含む最大区間[l,r)を求める．O(N).
template <typename Type, class Compare = std::function<bool(const Type &, const Type &)> >
std::vector<std::pair<int, int> > largest_rectangle(
    const std::vector<Type> &h,
    const Compare &comp = [](const Type &a, const Type &b) -> bool { return a <= b; }) {
    const int n = h.size();
    std::vector<std::pair<int, int> > res(n, {0, n});  // res[i]:=(pair of [l,r)).
    std::stack<std::pair<Type, int> > st;
    // left side.
    for(int i = 0; i < n; ++i) {
        while(!st.empty() and comp(h[i], st.top().first)) st.pop();
        if(!st.empty()) res[i].first = st.top().second + 1;
        st.push({h[i], i});
    }
    // right side.
    st = std::stack<std::pair<Type, int> >();
    for(int i = n - 1; i >= 0; --i) {
        while(!st.empty() and comp(h[i], st.top().first)) st.pop();
        if(!st.empty()) res[i].second = st.top().second;
        st.push({h[i], i});
    }
    return res;
}

}  // namespace algorithm

#endif

#line 1 "algorithm/Others/largest_rectangle.hpp"



/**
 * @brief 最大長方形問題
 * @docs docs/Others/largest_rectangle.md
 */

#include <functional>
#include <stack>
#include <utility>
#include <vector>

namespace algorithm {

// 最大長方形問題．
// 各iにおいて，comp(H[i], H[] within [l,r))==true となるiを含む最大区間[l,r)を求める．O(N).
template <typename Type, class Compare = std::function<bool(const Type &, const Type &)> >
std::vector<std::pair<int, int> > largest_rectangle(
    const std::vector<Type> &h,
    const Compare &comp = [](const Type &a, const Type &b) -> bool { return a <= b; }) {
    const int n = h.size();
    std::vector<std::pair<int, int> > res(n, {0, n});  // res[i]:=(pair of [l,r)).
    std::stack<std::pair<Type, int> > st;
    // left side.
    for(int i = 0; i < n; ++i) {
        while(!st.empty() and comp(h[i], st.top().first)) st.pop();
        if(!st.empty()) res[i].first = st.top().second + 1;
        st.push({h[i], i});
    }
    // right side.
    st = std::stack<std::pair<Type, int> >();
    for(int i = n - 1; i >= 0; --i) {
        while(!st.empty() and comp(h[i], st.top().first)) st.pop();
        if(!st.empty()) res[i].second = st.top().second;
        st.push({h[i], i});
    }
    return res;
}

}  // namespace algorithm

Back to top page