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);
}