给定一个数组A,其中包含1,2,...,n的排列. 如果出现的所有数字都是连续数字(可能不是有序的话),则A[i..j]数组的子块A称为有效块A[i..j].
A[i..j]
A
给定一个A= [ 7 3 4 1 2 6 5 8] 有效块的数组[3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8]
A= [ 7 3 4 1 2 6 5 8]
[3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8]
给出O(n log n)算法来计算有效块的数量.
algorithm
algorithm ×1