Back to Leetcode

Readme

Others/2808.Minimum-Seconds-to-Equalize-a-Circular-Array/Readme.md

latest641 B
Original Source

2808.Minimum-Seconds-to-Equalize-a-Circular-Array

我们想,最终所有的元素会变成谁呢?假如说最后都变成2,那么我们就需要考察原数组里非2的元素需要多少次传播被影响到。比如说,数组里非2元素的分布如下:X X 2 X X X 2 X X,很显然我们只要考察相邻两个2之间的最大跨度即可。如果跨度为d,说明相邻两个2中间的那个元素需要d/2次传播才能变成2.

所以我们只需要记录数组里每种元素数值的index分布,得到该数值的最大跨度(注意首尾相接)。最终答案是取所有最大跨度里最小的那个。