Largest Rectangle (最大長方形) (dp/largest-rectangle.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 06:35:14+00:00
• Include: #include "dp/largest-rectangle.hpp"

ヒストグラム中の最大長方形の面積を求める。

ヒストグラムを左から見る。スタックに自分より左にあるヒストグラムの高さと位置を単調増加になるように管理すると効率的に解ける。

largest_rectangle

int64_t largest_rectangle(vector<T> height)

ヒストグラムが height のとき最大長方形の面積を返す。

計算量

• $O(N)$

Verified with

• test/verify/aoj-dpl-3-c.test.cpp

Code

#pragma once

#include <algorithm>
#include <cstdint>
#include <stack>
#include <vector>

template <typename T>
std::int64_t largest_rectangle(std::vector<T> height) {
  std::stack<int> st;
  height.push_back(0);
  std::vector<int> left(height.size());
  std::int64_t ret = 0;
  for (int i = 0; i < height.size(); i++) {
    while (!st.empty() && height[st.top()] >= height[i]) {
      ret = std::max(ret,
                     (std::int64_t)(i - left[st.top()] - 1) * height[st.top()]);
      st.pop();
    }
    left[i] = st.empty() ? -1 : st.top();
    st.emplace(i);
  }
  return (ret);
}

#line 2 "dp/largest-rectangle.hpp"

#include <algorithm>
#include <cstdint>
#include <stack>
#include <vector>

template <typename T>
std::int64_t largest_rectangle(std::vector<T> height) {
  std::stack<int> st;
  height.push_back(0);
  std::vector<int> left(height.size());
  std::int64_t ret = 0;
  for (int i = 0; i < height.size(); i++) {
    while (!st.empty() && height[st.top()] >= height[i]) {
      ret = std::max(ret,
                     (std::int64_t)(i - left[st.top()] - 1) * height[st.top()]);
      st.pop();
    }
    left[i] = st.empty() ? -1 : st.top();
    st.emplace(i);
  }
  return (ret);
}

Back to top page