【算法】2019年蓝桥杯-修改数组
题目描述
输入描述
输出描述
输入输出描述
[写题时的思路]
诶，这难道不是用map标记一下不就是过了吗？二话不说直接开map标记，想都不带想的，然后直接WA了一发。看着红红的WA，再看看数据范围，发现原来是TLE了，10的6次方，每次都自身＋1，肯定会超时，于是又陷入了沉思......
打开题目标签，发现这个题用到了并查集，可是当我再看了一眼题目，并没有发觉到使用的有并查集，因为这其中并没有使用合并功能，想了半天最后WA了几发之后还是没有找到正确的解题思路，于是去看题解.......
[立正与挨打]
看完题解之后，再去看题目描述瞬间茅塞顿开，根据题目描述，如果当前数字前边出现过的话，那么我们就把当前这个数字+1，直至当前这个数字在前面数字没有出现过，确实是并查集查找的功能。
每次输出没出现的数字过后都把当前数字的父节点+1。
输出的是当前数字的父节点的值，使用并查集查找到根。
数据范围一定要初始化到边界，不然就会WA。
只知道并查集可以合并和查找集合的功能，但却忽略了可以查找到根，确实是对并查集掌握不熟，即便是后续WA了几发之后还是没想出这种解法，即便是后续输入的数字比前面的数字小，但是在每次维护根的时候还是可以查找到最大的根，一个很不错的题目，又增加了并查集的使用模型。
反思：刷题不足，见的题目类型仍然太少，算法模板的运用永远只有那几种模型。
