最长平台的新算法

最长平台问题描述如下：

一个从小到大排列的数组，这个数组中的一个平台就是连续的一段值相同的元素。例如：122333445中22，333等都是平台，333为最长平台。

一般常见的算法是一个计算机科学家首先给出的。

	private static int f1(int[] array) {

		if (array == null || array.length == 0)
			return 0;

		int length = 1;

		for (int i = 1; i < array.length; i++) {
			if (array[i] == array[i - length])
				length++;
		}

		return length;
	}

这段代码的确是简洁优雅的，但是在效率上不是很好。

最长平台有一些特点可以利用，从而使得算法的效率更高。
一个分界点元素指该元素和它的前一个元素不相等。
1 从一个分界点开始剩下的元素个数<=length，则可以直接返回。
2 从一个分界点开始找最大平台，没有必要依次顺序查找，直接跳到该（分界点的坐标+length）的元素进行查找。
  如果（分界点的坐标+length）也是一个分界点，则从原来的分界点到新的分界点（分界点的坐标+length）之间的 元素可以丢掉，从新的分界点重新开始查找最长平台。
  如果（分界点的坐标+length）不是一个分界点，则它有可能在一个最长平台中，判断之，然后继续。
这里主要是考虑到当前最长平台的长度，算法考虑该长度可以跳过一些元素进行处理。

	/**
	 * 最长平台更快的算法
	 */
	private static int f2(int[] array) {

		if (array == null || array.length == 0)
			return 0;

		// 下一个要检测的位置,保证array[next]!=array[next-1]。
		int next = 1;

		for (; next < array.length && array[next] == array[0]; next++)
			;

		// 第一个平台的长度,next>=1。
		int length = next;

		while (next < array.length) {

			// 如果剩下的元素个数<=length，则不可能有最长平台了
			if (array.length - next <= length) {
				break;
			}

			// 向前跳跃length+1,到next+length处进行检查，如果array[next+length]!=array[next+length-1],则
			// next - (next+length-1)这段数据可以丢弃.
			if (array[next + length] != array[next + length - 1]) {
				next = next + length;
			} else {
				// 这个相等的值所在的平台的值.
				int value = array[next + length];

				// 这个相等的值所在的平台的最后一个坐标.
				int endIndex = next + length + 1;
				for (; endIndex < array.length && array[endIndex] == value; endIndex++)
					;
				endIndex = endIndex - 1;

				// 向后跳跃length+1,如果相等，则这个平台是最大平台.
				if (array[endIndex - length] == value) {

					int startIndex = endIndex - length - 1;
					for (; array[startIndex] == value; startIndex--)
						;

					// 更新最大平台的值
					length = endIndex - startIndex;
				}

				next = endIndex + 1;

			}
		}

		return length;
	}

code是比上一个复杂一些，但是速度有了很大的提高，大约提高60%以上。

还有改进的余地，如果在查找一个平台的最后一个坐标或者第一个坐标，可以用2分查找。

这个代码简洁是简洁，但是错的....
f1(new int[]{1,1,2,3,2}) == 3

一个从小到大排列的数组

囧...
这样就简单了：

public static int maxSize(int[] array){
           if(array == null) return 0;
           int size = 0;
           int start = 0;
           while(start + size < array.length){
               start += size;
               int elem = array[start];
               if(array[start - size] != elem){
                   for(;array[start - 1] == elem;start --);
                   continue;
               }
               for(;start < array.length && array[start] == elem;size ++,start ++);
           }
           return size;
       }

这个算法还是比较简单的,请问一下什么场景会用到此算法,能否举一二例子

是啊，还真不知道有这个算法

楼主，能不能说说为什么你的算法效率高。能解释一下吗？从程序结构上看，空间和时间复杂度都比原来那个的高啊。

空间复杂度原来的算法是很好的。
时间复杂度，新的算法是比较好的。

原有的算法的复杂度是n。这个比较简单的可以看出来，它的过程是一个一个的数去测试。它的缺点是没有利用现有的知识。

新的算法利用了一些现有知识。从而不必比每个元素都进行处理。从而使得算法的效率更高。


可以利用的地方。
一个分界点元素指该元素和它的前一个元素不相等。
1 从一个分界点开始剩下的元素个数<=length，则可以直接返回。
2 从一个分界点开始找最大平台，没有必要依次顺序查找，直接跳到该（分界点的坐标+length）的元素进行查找。
  如果（分界点的坐标+length）也是一个分界点，则从原来的分界点到新的分界点（分界点的坐标+length）之间的 元素可以丢掉，从新的分界点重新开始查找最长平台。
  如果（分界点的坐标+length）不是一个分界点，则它有可能在一个最长平台中，判断之，然后继续。
这里主要是考虑到当前最长平台的长度，算法考虑该长度可以跳过一些元素进行处理。

LZ 你的改进党的算法有很大问题：

测试一下这组数据吧：  1,1,1,2,2,3,3,3,3

经典算法确实有一些“比较”次数感觉上是没有必要的，但是不能根据当前的length就认定下一次的平台一定可以越过length的长度不参与比较。

就比如上面的例子，1,1,1说明length=3，你认为后面的平台可以越过3次比较吗，也就是next=4--next=6这三个数都可以丢弃吗，注意你丢弃了2,2,3,  本来4个3的平台你丢掉了一个。

我最开始觉得优化确实可以跳跃，但是后来发现，跳跃多少不是一个简单的问题。这和每个平台最开始的分界点有关。

我也在考虑这个算法的优化问题，但目前还没有想到，我们可以一起来思考。有进展了我们相互通知哈。嘻嘻.... 

另外，交个朋友，我喜欢对算法优化专研的朋友。