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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "dp/largest-rectangle.hpp"

概要

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

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

• largest_rectangle(height): ヒストグラムが height のとき最大長方形の面積を返す.

計算量

• $O(N)$

Verified with

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

Code

template <typename T>
int64_t largest_rectangle(vector<T> height) {
  stack<int> st;
  height.push_back(0);
  vector<int> left(height.size());
  int64_t ret = 0;
  for (int i = 0; i < height.size(); i++) {
    while (!st.empty() && height[st.top()] >= height[i]) {
      ret = max(ret, (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 1 "dp/largest-rectangle.hpp"
template <typename T>
int64_t largest_rectangle(vector<T> height) {
  stack<int> st;
  height.push_back(0);
  vector<int> left(height.size());
  int64_t ret = 0;
  for (int i = 0; i < height.size(); i++) {
    while (!st.empty() && height[st.top()] >= height[i]) {
      ret = max(ret, (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