遍历有序数组统计值对数量，寻求优雅实现方案

嘿，既然你的数组已经是有序的了，咱们完全可以利用这个特性搞出高效又优雅的实现，犯不着暴力遍历所有数对浪费时间！下面给你几个适配不同场景的可行思路：

如果你的数组是严格升序且没有重复元素，那问题就超简单——每个元素后面的所有元素都比它大，有效数对的总数就是从n个元素中选2个的组合数：
总数 = n * (n - 1) // 2
举个例子，数组[1,2,3,4]的有效数对就是4*3/2=6组，完全符合预期。

如果数组里存在重复元素，上面的公式就不适用了。这时候我们可以遍历每个元素，借助二分查找快速定位第一个比当前元素大的位置，这样就能算出当前元素能和后面多少个元素组成有效数对，累加所有结果即可。

Python代码示例：

import bisect

def count_valid_pairs(arr):
    total = 0
    arr_len = len(arr)
    for idx in range(arr_len):
        # 从当前元素的下一位开始，找第一个大于arr[idx]的位置
        first_larger_pos = bisect.bisect_right(arr, arr[idx], idx + 1, arr_len)
        total += arr_len - first_larger_pos
    return total

这个方法的时间复杂度是O(n log n)，比暴力遍历的O(n²)高效得多，代码也很简洁易读。

因为数组是有序的，相同元素必然连续排列。我们可以通过一次遍历，统计每个元素的出现次数，同时记录前面所有比当前元素小的元素总个数，每次计算当前元素能贡献的有效数对（前面总个数 × 当前元素出现次数），最后累加所有结果。

Python代码示例：

def count_valid_pairs(arr):
    total = 0
    arr_len = len(arr)
    if arr_len < 2:
        return 0
    
    prev_total = 0
    current_val = arr[0]
    current_count = 1
    
    for idx in range(1, arr_len):
        if arr[idx] == current_val:
            current_count += 1
        else:
            # 当前元素组与前面所有元素组成的有效数对
            total += prev_total * current_count
            prev_total += current_count
            current_val = arr[idx]
            current_count = 1
    # 处理最后一组元素
    total += prev_total * current_count
    return total

这个方法的时间复杂度是O(n)，空间复杂度是O(1)，是效率最高的方案，完美利用了有序数组的特性，代码也相当优雅。

内容的提问来源于stack exchange，提问作者Martin Muldoon