Largest rectangle in histogram (tools/largest_rectangle_in_histogram.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-01-25 08:45:50+09:00
• Include: #include "tools/largest_rectangle_in_histogram.hpp"

template <typename Iterator>
typename ::std::iterator_traits<Iterator>::value_type largest_rectangle_in_histogram(Iterator begin, Iterator end);

It returns the area of the largest rectangle in a given histogram.

Constraints

• begin $\leq$ end

Time Complexity

• $O(n)$ where $n$ is end - begin

License

• CC0

Author

• anqooqie

Depends on

• chmax function (tools/chmax.hpp)

Verified with

• tests/largest_rectangle_in_histogram.test.cpp

Code

#ifndef TOOLS_LARGEST_RECTANGLE_IN_HISTOGRAM_HPP
#define TOOLS_LARGEST_RECTANGLE_IN_HISTOGRAM_HPP

#include <iterator>
#include <stack>
#include <utility>
#include <tuple>
#include "tools/chmax.hpp"

namespace tools {
  template <typename InputIterator>
  typename ::std::iterator_traits<InputIterator>::value_type largest_rectangle_in_histogram(const InputIterator& begin, const InputIterator& end) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;

    T result = 0;
    ::std::stack<::std::pair<T, T>> dp;
    for (auto [i, it, breaks] = ::std::make_tuple(0, begin, false); !breaks; ++i, breaks = it == end, it = ::std::next(it, breaks ? 0 : 1)) {
      const T v = it != end ? *it : 0;
      if (dp.empty() || dp.top().second < v) {
        dp.emplace(i, v);
      } else if (dp.top().second > v) {
        T leftmost;
        while (!dp.empty() && dp.top().second > v) {
          leftmost = dp.top().first;
          ::tools::chmax(result, dp.top().second * (i - dp.top().first));
          dp.pop();
        }
        if (dp.empty() || dp.top().second < v) {
          dp.emplace(leftmost, v);
        }
      }
    }

    return result;
  }
}

#endif

#line 1 "tools/largest_rectangle_in_histogram.hpp"



#include <iterator>
#include <stack>
#include <utility>
#include <tuple>
#line 1 "tools/chmax.hpp"



#include <type_traits>
#line 6 "tools/chmax.hpp"

namespace tools {

  template <typename M, typename N>
  bool chmax(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(lhs, rhs);
    } else {
      updated = lhs < rhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 9 "tools/largest_rectangle_in_histogram.hpp"

namespace tools {
  template <typename InputIterator>
  typename ::std::iterator_traits<InputIterator>::value_type largest_rectangle_in_histogram(const InputIterator& begin, const InputIterator& end) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;

    T result = 0;
    ::std::stack<::std::pair<T, T>> dp;
    for (auto [i, it, breaks] = ::std::make_tuple(0, begin, false); !breaks; ++i, breaks = it == end, it = ::std::next(it, breaks ? 0 : 1)) {
      const T v = it != end ? *it : 0;
      if (dp.empty() || dp.top().second < v) {
        dp.emplace(i, v);
      } else if (dp.top().second > v) {
        T leftmost;
        while (!dp.empty() && dp.top().second > v) {
          leftmost = dp.top().first;
          ::tools::chmax(result, dp.top().second * (i - dp.top().first));
          dp.pop();
        }
        if (dp.empty() || dp.top().second < v) {
          dp.emplace(leftmost, v);
        }
      }
    }

    return result;
  }
}

Back to top page