Quiz

最大長方形
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B&lang=jp
- 壁のあるグリッド内で作れる最大長方形の面積を求めよ

AC

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4010799#1

解法

（１）まず、各行を底としたヒストグラムを求める
（２）次に、ヒストグラム内の最大長方形を求める

（１）

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

f:id:peroon:20191127195732p:plain

（２）

こちらが本題
スタックを使うことで最大長方形がO(W)で求められ、底辺を全探索する(O(H))ので(2)の計算量はO(WH)
参考：http://algorithms.blog55.fc2.com/blog-entry-132.html
ヒストグラムの最大長方形を土台として、底辺の全探索（↓）

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