ヒストグラム中の最大長方形 (largest rectangle in a histogram)
(include/emthrm/dynamic_programming/largest_rectangle.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/dynamic_programming/largest_rectangle.hpp"

時間計算量

$O(N)$

仕様

名前	戻り値
template <typename T> long long largest_rectangle(const std::vector<T>& height);	高さ $\mathrm{height}$ で表されるヒストグラム中の長方形の最大面積

参考文献

• https://ei1333.github.io/luzhiled/snippets/dp/largest-rectangle.html

TODO

• http://algorithms.blog55.fc2.com/blog-entry-133.html
• 最大正方形
  • https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_A
• 最大長方形
  • https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_B

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/DPL_3_C/review/4082202/emthrm/C++14

Verified with

• 動的計画法/ヒストグラム中の最大長方形 (test/dynamic_programming/largest_rectangle.test.cpp)

Code

#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

Back to top page