競プロ初心者 ヒストグラム ループ減らしたい 二次元配列

Question

初期値が0のカウンターがN個ある。（N次元配列）
カウンターには、次のオペレーションが存在する。

increase(X)：カウンターXを1インクリメントする。
max counter：全てのカウンターを、現在のカウンターの最大値に設定する。
これらのオペレーションを表す、M個の整数を含む配列Aがあるとする。

A[K] = X（ただし 1 <= X <= N）の場合、オペレーションKは increase(X) を表す。
A[K] = N+1の場合、オペレーションKは max counter を表す。
全てのオペレーションを実行した後のカウンターを求めよ。

ただし、
NとMの範囲は[1..100,000]とする。
配列Aはの要素は[1..N + 1]の範囲の整数とする。

例

入力 A = [3, 4, 4, 6, 1, 4, 4], N=5
    出力-> [3, 2, 2, 4, 2]

各オペレーション後のカウンターの状態：
    [0, 0, 1, 0, 0]
    [0, 0, 1, 1, 0]
    [0, 0, 1, 2, 0]
    [2, 2, 2, 2, 2]
    [3, 2, 2, 2, 2]
    [3, 2, 2, 3, 2]
    [3, 2, 2, 4, 2]

これで、

def solution(N, A):
    k=[0]*N
    for i in A:
        if i<=N:
            k[i-1]+=1
        else:
            k=[max(k)]*N
    return k

としたとき、O(N*M)となって数が大きいときに通りません。
どうすればいいのでしょう。

Answer 1

最大値を取るときにゼロのところを調べるのは無駄ですね。
どうすれば、それを避けることができるかを考えてください。

Comments

[MycoChild]

なるほど。
これでO(N+M)で通りました。
```
def solution(N, A):
k=[0]*N
maxc=0#最頻度の数
tmp=0
for i in A:
if i<=N:
if k[i-1]<maxc:#マックスが起こった後の操作
k[i-1]=maxc+1
else:
k[i-1]+=1
if tmp<k[i-1]:#更新したやつが最頻なら格納
tmp=k[i-1]
else:#N+1のとき
maxc=tmp#これまでの最頻値を保存
for i in range(N):#小さいやつをmaxcに更新
if k[i]<maxc:
k[i]=maxc
return k
```