Largest rectangle in histogram
(Mylib/Typical/max_rectangle_in_histogram.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• max_rectangle_in_histogram(T h[N])
  • Time complexity $O(N)$

Requirements

Notes

Problems

• AOJ DPL_3_C Largest Rectangle in a Histogram

References

Required by

• Largest rectangle (Mylib/Typical/max_rectangle.cpp)

Verified with

• test/aoj/DPL_3_B/main.test.cpp
• test/aoj/DPL_3_C/main.test.cpp

Code

#pragma once
#include <stack>
#include <utility>
#include <vector>

namespace haar_lib {
  template <typename T>
  T max_rectangle_in_histogram(const std::vector<T> &h) {
    std::stack<std::pair<T, int>> st;
    T ret = 0;

    for (size_t i = 0; i < h.size(); ++i) {
      if (st.empty()) {
        st.emplace(h[i], i);
      } else if (st.top().first < h[i]) {
        st.emplace(h[i], i);
      } else if (st.top().first > h[i]) {
        int j = i;
        while (not st.empty() and st.top().first > h[i]) {
          ret = std::max(ret, st.top().first * ((T) i - st.top().second));
          j   = st.top().second;
          st.pop();
        }
        st.emplace(h[i], j);
      }
    }

    while (not st.empty()) {
      ret = std::max(ret, st.top().first * ((T) h.size() - st.top().second));
      st.pop();
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Typical/max_rectangle_in_histogram.cpp"
#include <stack>
#include <utility>
#include <vector>

namespace haar_lib {
  template <typename T>
  T max_rectangle_in_histogram(const std::vector<T> &h) {
    std::stack<std::pair<T, int>> st;
    T ret = 0;

    for (size_t i = 0; i < h.size(); ++i) {
      if (st.empty()) {
        st.emplace(h[i], i);
      } else if (st.top().first < h[i]) {
        st.emplace(h[i], i);
      } else if (st.top().first > h[i]) {
        int j = i;
        while (not st.empty() and st.top().first > h[i]) {
          ret = std::max(ret, st.top().first * ((T) i - st.top().second));
          j   = st.top().second;
          st.pop();
        }
        st.emplace(h[i], j);
      }
    }

    while (not st.empty()) {
      ret = std::max(ret, st.top().first * ((T) h.size() - st.top().second));
      st.pop();
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page