列表支配元素统计功能实现求助（附错误Python代码）

需求回顾 #

列表中的**支配元素（dominator）**指该元素右侧所有元素（不仅是紧邻右侧的元素）都严格小于它，需要统计这类元素的总数量。

原代码问题分析 #

你当前的代码逻辑不符合需求：

• 原代码中，只要当前元素比右侧任意一个元素大，就会给countDem加1，这会导致重复计数，且错误地将“仅大于部分右侧元素”的元素也算作支配元素。
• 举个例子：列表[5,3,4]，原代码会因为5>3加1、5>4加1，最终返回2，但实际上只有5是支配元素，正确结果应为1。

正确解法 #

方法1：暴力优化法（逻辑直观）

遍历每个元素，检查其右侧所有元素是否都严格小于它，只有全部满足时才计数：

def count_dominators(digits):
    count = 0
    n = len(digits)
    for i in range(n):
        is_dominator = True
        # 检查当前元素右侧所有元素
        for j in range(i + 1, n):
            if digits[i] <= digits[j]:
                is_dominator = False
                break  # 只要有一个元素不满足，直接终止检查
        if is_dominator:
            count += 1
    return count

方法2：高效遍历法（时间复杂度O(n)）

从右往左遍历，记录右侧已遍历元素的最大值：

• 最后一个元素右侧没有元素，必然是支配元素，初始计数设为1。
• 每往左遍历一个元素，若它大于当前记录的右侧最大值，说明它比右侧所有元素都大，计数加1并更新最大值。

def count_dominators(digits):
    if not digits:
        return 0
    count = 1
    max_right = digits[-1]
    # 从倒数第二个元素开始向左遍历
    for num in reversed(digits[:-1]):
        if num > max_right:
            count += 1
            max_right = num
    return count

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