CFR 803 B. Distances to Zero ( Ad hoc )
題意:
給一個數列,其中至少有一個元素為 0。對每一個位置輸出離它最近的 0 的距離。
制約:
The first line contains integer n (1 ≤ n ≤ 2e5) — length of the array a. The second line contains integer elements of the array separated by single spaces ( - 1e9 ≤ ai ≤ 1e9).
解法:
從左邊往右掃一次,記錄最靠右的 0 的位置更新。再由右往左做一次。
時間 / 空間複雜度:
O( N )
N = int( input() ) A = list( map( int, input().split() ) ) ans = [ N for i in range( N ) ] prev = -N for i in range( N ): if A[ i ] == 0: prev = i ans[ i ] = i - prev prev = N + N for i in range( N - 1, -1, -1 ): if A[ i ] == 0: prev = i ans[ i ] = min( ans[ i ], prev - i ) print( *ans )