ヒストグラム内の最大長方形を求める

Quiz

AC

解法

(1)

  • 列ごとに下にカウントしていけばO(WH)で求まる

f:id:peroon:20191127195732p:plain

(2)

f:id:peroon:20210124005734p:plain

全体の計算量

  • (1)がO(WH), (2)がO(WH)なので、全体としてもO(WH)

code

// ヒストグラムを与えると、最大の長方形の面積を返します
// 計算量 O(N)
ll largest_rectangle_in_a_histogram(VI& V){
  ll ma = 0;
  stack<PII> st;
  ll N = SZ(V);
  rep(i, N){
    ll h = V[i];
    // スタックが空ならそのまま積む
    if(st.size()==0){
      st.push({h,i});
    }
    // 高さが同じ
    else if(st.top().first==h){
      continue;
    }
    // より高いものが来た
    else if(st.top().first<h){
      st.push({h,i});
    }
    // より低いものが来た
    else{
      ll last_pos;
      // スタックの方が高いものは全部取り除いて精算する(面積を求める)
      while(st.size()>0 && st.top().first>h){
        auto pa = st.top(); st.pop();
        ll area = pa.first * (i-pa.second);
        chmax(ma, area);
        last_pos = pa.second;
      }
      // 今回の値をスタックに積む(位置は、最後にスタックから取り除いたものの位置)
      st.push({h, last_pos});
    }
  }
  // stackに残っている分
  while(st.size()>0){
    auto pa = st.top(); st.pop();
    ll area = pa.first * (N-pa.second);
    chmax(ma, area);
  }
  return ma;
}

補足

類題

verified