BOJ. Histogram (1725)

Problem: BOJ 1725 — Histogram · 한국어 · 日本語

For each bar, consider the widest rectangle in which that bar is the shortest. Its left and right boundaries are the nearest bars strictly shorter than it. Scanning from left to right with a monotonic stack lets us discover those boundaries as soon as a shorter bar appears.

The stack stores indices whose heights are in nondecreasing order. When the current bar is lower than the height at the top, that top index can no longer extend to the right: the current index is its first smaller bar on the right. After popping it, the new top is the nearest smaller bar on the left, so the rectangle width is i - left - 1; if the stack is empty, the width is i. We pop equal heights as well, so each surviving index has a strictly lower stack predecessor and equal-height bars are handled consistently.

After all input bars, a sentinel height of 0 flushes every remaining index. No recursive calls are needed. Every index is pushed once and popped once, giving O(N) time and O(N) auxiliary space. Heights, widths, and areas are stored in long long so the area multiplication remains safe.

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<long long> height(n);
  for (long long &bar : height) cin >> bar;

  vector<int> st;
  st.reserve(n);
  long long answer = 0;

  for (int i = 0; i <= n; ++i) {
    const long long current = (i == n ? 0 : height[i]);
    while (!st.empty() && height[st.back()] >= current) {
      const long long barHeight = height[st.back()];
      st.pop_back();
      const int width = st.empty() ? i : i - st.back() - 1;
      answer = max(answer, barHeight * width);
    }
    if (i < n) st.push_back(i);
  }

  cout << answer;
}