題目描述

輸入描述

輸出描述

輸入輸出描述

[寫(xiě)題時(shí)的思路]

????????誒，這難道不是用map標(biāo)記一下不就是過(guò)了嗎？二話(huà)不說(shuō)直接開(kāi)map標(biāo)記，想都不帶想的，然后直接WA了一發(fā)?？粗t紅的WA，再看看數(shù)據(jù)范圍，發(fā)現(xiàn)原來(lái)是TLE了，10的6次方，每次都自身＋1，肯定會(huì)超時(shí)，于是又陷入了沉思......

????????打開(kāi)題目標(biāo)簽，發(fā)現(xiàn)這個(gè)題用到了并查集，可是當(dāng)我再看了一眼題目，并沒(méi)有發(fā)覺(jué)到使用的有并查集，因?yàn)檫@其中并沒(méi)有使用合并功能，想了半天最后WA了幾發(fā)之后還是沒(méi)有找到正確的解題思路，于是去看題解.......

[立正與挨打]

????????看完題解之后，再去看題目描述瞬間茅塞頓開(kāi)，根據(jù)題目描述，如果當(dāng)前數(shù)字前邊出現(xiàn)過(guò)的話(huà)，那么我們就把當(dāng)前這個(gè)數(shù)字+1，直至當(dāng)前這個(gè)數(shù)字在前面數(shù)字沒(méi)有出現(xiàn)過(guò)，確實(shí)是并查集查找的功能。

• 每次輸出沒(méi)出現(xiàn)的數(shù)字過(guò)后都把當(dāng)前數(shù)字的父節(jié)點(diǎn)+1。

• 輸出的是當(dāng)前數(shù)字的父節(jié)點(diǎn)的值，使用并查集查找到根。

• 數(shù)據(jù)范圍一定要初始化到邊界，不然就會(huì)WA。

????????只知道并查集可以合并和查找集合的功能，但卻忽略了可以查找到根，確實(shí)是對(duì)并查集掌握不熟，即便是后續(xù)WA了幾發(fā)之后還是沒(méi)想出這種解法，即便是后續(xù)輸入的數(shù)字比前面的數(shù)字小，但是在每次維護(hù)根的時(shí)候還是可以查找到最大的根，一個(gè)很不錯(cuò)的題目，又增加了并查集的使用模型。

????????反思：刷題不足，見(jiàn)的題目類(lèi)型仍然太少，算法模板的運(yùn)用永遠(yuǎn)只有那幾種模型。