c++ - 查找数组中连续空白的最大长度

Question

有一个用char元素填充的数组，你能建议一个最有效的方法来找到连续空白的最大长度吗？

Answer 1

从左到右扫描数组，记下空白。当您到达一个非空白字符时，请检查该计数是否与当前最大值相对应；如果它更高，它就成为新的最大值。跳过数组中的这个最大数字 - 如果它不是空白，你知道间隔不能包含最大空白。否则向后搜索到空白开始的地方 - 找到设置你的计数并从你之前跳到的地方继续。

我相信最坏情况下的性能是 O(n)，最好情况下是 O(sqrt(n))，因为在每次跳过时有一个 sqrt(n) 开始的空白后面跟着非空白点(导致重复跳到数组末尾)。