C#如何查找元素均大于K的最长连续子数组的首尾下标

实现思路 #

• 采用单次遍历方案，时间复杂度为O(N)，仅需常数额外空间
• 遍历过程中维护4个状态变量：
  • currentStart：当前正在统计的、所有元素均大于K的连续子数组的起始下标，无符合条件的连续段时设为-1
  • maxLen：目前找到的最长符合条件子数组的长度
  • bestStart、bestEnd：最长符合条件子数组的首尾下标
• 遍历结束后需要额外判断数组末尾的连续段是否为最长段，避免遗漏边界情况

完整代码 #

static void Main(string[] args)
{
    string[] fRow = Console.ReadLine().Split(' ');
    int N = int.Parse(fRow[0]);
    int K = int.Parse(fRow[1]);
    int[] H = new int[N];
    for (int i = 0; i < N; i++)
    {
        H[i] = int.Parse(Console.ReadLine());
    }

    // 查找逻辑开始
    int currentStart = -1;
    int maxLen = 0;
    int bestStart = 0;
    int bestEnd = 0;

    for (int i = 0; i < N; i++)
    {
        if (H[i] > K)
        {
            // 符合条件，开启新段或延续当前段
            if (currentStart == -1)
            {
                currentStart = i;
            }
        }
        else
        {
            // 不符合条件，结算之前的连续段
            if (currentStart != -1)
            {
                int currentLen = i - currentStart;
                if (currentLen > maxLen)
                {
                    maxLen = currentLen;
                    bestStart = currentStart;
                    bestEnd = i - 1;
                }
                currentStart = -1;
            }
        }
    }

    // 结算数组末尾可能存在的符合条件的连续段
    if (currentStart != -1)
    {
        int currentLen = N - currentStart;
        if (currentLen > maxLen)
        {
            maxLen = currentLen;
            bestStart = currentStart;
            bestEnd = N - 1;
        }
    }

    // 输出结果
    Console.WriteLine($"{bestStart} {bestEnd}");
}

运行验证 #

针对你给出的示例输入，代码会识别到最长连续段起始下标为1，结束下标为3，输出1 3，和预期结果一致。如果存在多个长度相同的最长连续段，代码会返回第一个出现的段的下标。

内容的提问来源于stack exchange，提问作者Gergő Szatmári