基于Timestamp过滤含间断连续重复值的列表，求更高效方案

需求说明 #

处理时序数据列表时需遵循以下规则：

• 过滤后列表中的值在0和1之间交替出现
• 若存在连续重复值，仅保留该组中Timestamp最大的条目

原始数据 #

期望过滤结果 #

现有实现的问题 #

你当前的for循环逻辑正确，但在每个连续值段中使用Skip+Take+OrderByDescending获取最大时间戳元素，会带来额外的排序开销（时间复杂度为O(n log k)，k为当前段长度），大数据量场景下效率偏低。

高效解决方案：单次遍历O(n)实现 #

通过一次遍历完成过滤，全程跟踪当前连续值段中时间戳最大的元素，遇到值变化时将该元素加入结果列表，同时更新跟踪对象。这种方式时间复杂度为O(n)，空间复杂度为O(1)（除结果存储），性能大幅提升。

代码实现 #

class DataPoint
{
    public TimeSpan Timestamp { get; set; }
    public int Value { get; set; }
}

class Program
{
    static void Main(string[] args)
    {
        List<DataPoint> dataPoints = new List<DataPoint>
        {
            new DataPoint { Timestamp = TimeSpan.Parse("08:10"), Value = 0 },
            new DataPoint { Timestamp = TimeSpan.Parse("08:15"), Value = 0 },
            new DataPoint { Timestamp = TimeSpan.Parse("08:20"), Value = 1 },
            new DataPoint { Timestamp = TimeSpan.Parse("08:25"), Value = 0 },
            new DataPoint { Timestamp = TimeSpan.Parse("08:30"), Value = 1 },
            new DataPoint { Timestamp = TimeSpan.Parse("08:35"), Value = 1 },
            new DataPoint { Timestamp = TimeSpan.Parse("08:50"), Value = 1 },
            new DataPoint { Timestamp = TimeSpan.Parse("08:55"), Value = 0 }
        };

        var filteredData = new List<DataPoint>();
        if (dataPoints.Count == 0)
        {
            return;
        }

        // 初始化当前段的最大时间戳元素
        DataPoint currentMax = dataPoints[0];

        foreach (var point in dataPoints.Skip(1))
        {
            if (point.Value == currentMax.Value)
            {
                // 同一值段，更新最大时间戳元素
                if (point.Timestamp > currentMax.Timestamp)
                {
                    currentMax = point;
                }
            }
            else
            {
                // 值发生变化，将当前段最大元素加入结果
                filteredData.Add(currentMax);
                currentMax = point;
            }
        }

        // 加入最后一个段的最大元素
        filteredData.Add(currentMax);

        foreach (var dataPoint in filteredData)
        {
            Console.WriteLine($"Timestamp: {dataPoint.Timestamp}, Value: {dataPoint.Value}");
        }
    }
}

实现说明 #

1. 初始化：将第一个元素设为当前值段的最大元素
2. 遍历后续元素：
   • 若当前元素值与currentMax相同，比较时间戳，更新currentMax为时间戳更大的元素
   • 若值不同，将currentMax加入结果列表，并将当前元素设为新的currentMax
3. 收尾：遍历结束后，将最后一个值段的currentMax加入结果

这种方式避免了不必要的子序列排序和集合操作，全程仅遍历数据一次，大数据量场景下性能优势明显。

备选方案：LINQ Aggregate实现 #

若偏好LINQ风格代码，可使用Aggregate实现同样的O(n)逻辑，代码更简洁，适合数据量不大的场景：

var filteredData = dataPoints.Aggregate(
    new List<DataPoint>(),
    (acc, point) =>
    {
        if (acc.Count == 0)
        {
            acc.Add(point);
        }
        else
        {
            var last = acc.Last();
            if (last.Value == point.Value)
            {
                // 替换为时间戳更大的元素
                if (point.Timestamp > last.Timestamp)
                {
                    acc[acc.Count - 1] = point;
                }
            }
            else
            {
                acc.Add(point);
            }
        }
        return acc;
    });

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