ABC189-C Mandarin Orange 解説（stack 活用編）

$O(N)$ で解きます。$O(N \log N)$ はこちら

問題

問題ページ

概要

$$ \max _ {1 \leq l \leq r \leq n} \left\lbrace (r - l + 1) \cdot \min _ {l \leq i \leq r} a _ i \right\rbrace $$

解法

前回の続きです。今回は皿の大きさ順ではなく、シンプルに左から見ていくことにします。

再び「その皿のミカンを全て取るとした時、収穫範囲を左右どこまで広げられるか」を考えます。 ここで、左に伸ばすことと右に伸ばすことはお互いに影響しないので、まず「どこまで左に伸ばせるか」を考えます。

どこまで伸ばせるかというと、「自分より小さな皿のうち最も近いもの」（境界）の一個手前までです。全ての皿について、境界を順番に計算していきます。 ある皿の左側がこのようになっていたとします。

たくさんのミカン

この時、次に見る皿の大きさに関わらず、 $11$ の皿は絶対に境界にはなりません。右隣にある $2$ の皿の方が小さく、しかも必ず次に見る皿に近くなってしまうからです。同様に、 $4, 19$ の皿も境界にはなりません。このように考えると、境界の候補は以下のように単調に増加する数列として表されます。

残ったミカンは単調増加

単調なので、二分探索によって境界の位置を求めることができます。

その後、この列に今見た皿が追加されますが、新たに $9, 80$ の皿が絶対に境界にならなくなりました。よって、この皿も削除してしまいます。

結局単調増加のまま

この時、左側で残っている皿が単調増加であることから、削除するべき大きい皿は常に末尾に固まっているはずなので、末尾が自分より大きい限り削除を続ければよいです。 削除が終わったとき、末尾にあるものは先程二分探索で見つけた境界のはずです。ということは、先に削除の操作を行ってしまえば二分探索をしなくても境界を求めることができるということです。

よって、左側にある皿を蓄えるstackを用意して、

1. 自分より大きな皿を削除（末尾からのpopを繰り返す）
2. 境界を記録して、自分を追加

を繰り返すことで、全ての皿について境界（収穫範囲の左端）を求めることができます。 push、popの計算量は $O(1)$ であり、全ての皿は高々一度づつしか追加・削除されないので、計算量は合計で $O(N)$ です。

同様にこれを右側から行えば、それぞれの収穫範囲の右端も求めることができます。よって全ての皿に対して最大の収穫範囲が求まるので、あとはそれらのうち答えが最大になるものを計算すれば良いです。 計算量は全体で $O(N)$ です。

実装

境界を探すのを簡単にするため、stackには皿の大きさではなくindexを入れています。 また、stackが空になった時の処理を単純化するため予め番兵を入れています。

n = int(input())
a = list(map(int, input().split()))
a += [0] # 番兵

left = [0] * n # left[i]: 皿iの左の境界
right = [0] * n

# 左から見る
st = [-1] # 番兵
for i in range(n):
    while a[st[-1]] >= a[i]:
        st.pop()
    left[i] = st[-1]
    st.append(i)

# 右から
st = [n] # 番兵
for i in range(n-1, -1, -1):
    while a[st[-1]] >= a[i]:
        st.pop()
    right[i] = st[-1]
    st.append(i)

ans = max(a[i] * (right[i] - left[i] - 1) for i in range(n))
print(ans)

提出

提出コード(Python3)