@ninijia 在 Leetcode每日一题练习 ------ 2501. 数组中最长的方波 中发帖
从Leetcode 每日一题练习继续讨论:
2501. 数组中最长的方波
2501. Longest Square Streak in an Array
题解
本题先排序,因为我们要找的其实也是一个有序子序列(后一个数均是前一个数的平方,当然比前面的数字更大),在乱序的情况下很难通过一次遍历找到这样的序列,乱序时可能会遇到一个很大的数还需要后面判断是否有它的因子和以它为因子的数,这样我们要处理更多的可能性,而有序我们只需在遍历时判断是否是以前遇到过的数字的平方。
这里可以使用一个队列用于存放遍历过的数字的平方数和该数字对应的子序列当前的长度,遍历有序数组,判断当前数字是否是队列头部的数字,如果是则将头部弹出并将当前序列长度加1,同时向队列末尾插入当前弹出的数字的平方数。如果当前数字比队列头部数字大则同样弹出队列头部,如果比队列头部数字小则向队列末尾插入当前数字的平方数并将子队列长度...