Yuki 489 株に挑戦 ( Sliding Window )
題意:
買賣股票,買跟麥只做一次。必須滿足買的日期 i 和賣的日期 j 有 j - i <= D。求差額 * K,以及字典序最小的買賣日期。若無法得到正利潤,輸出 0 即可。
制約:
2 ≤ N ≤ 1e5
1 ≤ D < N
1 ≤ K ≤ 1e6
1 ≤ xi ≤ 1e6
解法:
努力寫了一次線段樹,但 python 也很給力的 TLE 了。
經典的滑動視窗:
window[ i ]: i - D ≤ window[ i ] < i 中最小的 window[ i ]。若不存在則為 -1。
用單調隊列維護下標的單調遞增和值的非嚴格單調遞增即可。
時間 / 空間複雜度:
O( N )
from collections import deque N, D, K = map( int, input().split() ) X = list( int( input() ) for i in range( N ) ) window = [ -1 for i in range( N ) ] dq = deque() for i in range( N ): while len( dq ) and i - dq[ 0 ] > D: dq.popleft() if len( dq ): window[ i ] = dq[ 0 ] while len( dq ) and X[ i ] < X[ dq[ len( dq ) - 1 ] ]: dq.pop() dq.append( i ) best = 0 bl, br = -1, -1 for i in range( N ): if window[ i ] == -1: continue if [ best, bl ] >= [ X[ i ] - X[ window[ i ] ], - window[ i ] ]: continue best = X[ i ] - X[ window[ i ] ] bl, br = - window[ i ], i print( best * K ) if best > 0: print( - bl, br )