最大長方形
(dp/maximal-rectangle.hpp)

• View this file on GitHub
• Last update: 2021-11-17 23:54:43+09:00
• Include: #include "dp/maximal-rectangle.hpp"

最大長方形

概要

短く言うと、ヒストグラム中の長方形の最大面積を求める。

非負整数列$A$を入力とする。非負整数$l,r,h$ $(l \leq r \lt N)$が$h \leq A_i$ $(l \leq i \leq r)$ を満たすとき、$h(r-l+1)$の最大値を求める。

使い方

• MaximalRectangle(buf): bufで非負整数列$A$を与える。求める最大値を返す。計算量$\mathrm{O}(\vert A \vert)$

Verified with

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

Code

#pragma once

long long MaximalRectangle(vector<long long> buf) {
  int N = buf.size();
  buf.push_back(0);
  using P = pair<long long, long long>;
  stack<P> st;
  long long mx = 0;
  for (int i = 0; i <= N; i++) {
    P rect{buf[i], i};
    if (st.empty() or st.top().first < rect.first) {
      st.push(rect);
    } else {
      int j = i;
      while (!st.empty() and st.top().first >= rect.first) {
        P pre = st.top();
        st.pop();
        mx = max(mx, pre.first * (i - pre.second));
        j = pre.second;
      }
      rect.second = j;
      st.push(rect);
    }
  }
  return mx;
}

/**
 * @brief 最大長方形
 * @docs docs/dp/maximal-rectangle.md
 */

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

long long MaximalRectangle(vector<long long> buf) {
  int N = buf.size();
  buf.push_back(0);
  using P = pair<long long, long long>;
  stack<P> st;
  long long mx = 0;
  for (int i = 0; i <= N; i++) {
    P rect{buf[i], i};
    if (st.empty() or st.top().first < rect.first) {
      st.push(rect);
    } else {
      int j = i;
      while (!st.empty() and st.top().first >= rect.first) {
        P pre = st.top();
        st.pop();
        mx = max(mx, pre.first * (i - pre.second));
        j = pre.second;
      }
      rect.second = j;
      st.push(rect);
    }
  }
  return mx;
}

/**
 * @brief 最大長方形
 * @docs docs/dp/maximal-rectangle.md
 */

Back to top page