滑動(dòng)窗口
流程:
左指針右指針初始在同一位置,同方向移動(dòng),
每次檢測(cè)左右指針之間的區(qū)域
不符合要求,右移右指針
符合要求則記錄,右移左指針
跳出條件:右指針右移失敗
需要關(guān)注的問(wèn)題
問(wèn)題描述
最大&條件:右移r到非法,記錄此時(shí)長(zhǎng)度為[l,r-1];然后右移l到合法
最小&條件:右移r到合法,右移l到非法,記錄此時(shí)長(zhǎng)度為[l,r]
lr之間的數(shù)據(jù)如何保存
set
map
340. 至多包含 K 個(gè)不同字符的最長(zhǎng)子串
map+統(tǒng)計(jì)字母出現(xiàn)的數(shù)組(***)
前綴最值
輔助數(shù)組:lmax,rmax表示從最左(右)到該點(diǎn)的最大數(shù)字。
左指針=0右指針=n-1,初始在數(shù)組兩邊,反方向移動(dòng),
處理+移動(dòng),根據(jù)情況辨別誰(shuí)先誰(shuí)后
每次比較左右指針的數(shù)值大小+然后處理指向數(shù)值小的指針,根據(jù)其lmax,rmax等計(jì)算題設(shè)的值,必要時(shí)更新最值
每次計(jì)算此時(shí)的結(jié)果,根據(jù)結(jié)果判斷哪個(gè)指針移動(dòng)
跳出條件:兩指針相遇
其他:
兩個(gè)或以上指針指向需要標(biāo)記的 index