algorithm - O(n) 中的连续子数组解决方案

Question

最近我遇到了一个问题，指出有一个整数数组，我们将得到一个通配符数字。我们需要遍历数组并形成一个子数组，使得

1. 通配符数字应该是子数组的最后一个元素(即: 如果 4 是通配符，则 {2,3,4} 有效，但 {2,4,3} 无效)。
2. 外卡号前的所有元素应小于那。 (即:如果 4 是外卡号码，则 {2,3,4} 有效，但 {5,2,4}无效)。
3. 外卡号不应在两个子数组之间合并。

输出应返回此类子数组的长度。

示例问题:如果数组是 {4,5,6,4,3,2,4,8,2,4} 并且通配符数字是 4，则输出应该是 7。(因为子数组是 {4}，{4 }, {3,2,4}, {2,4}).

我已经为这个问题编写了代码。但是我需要知道的是解决方案是否可以写成 O(n) 时间复杂度。还有一种方法可以通过单独查看问题来找到可能的最佳时间复杂度。

代码片段:

private static void solution(int[] array, int k)
    {
        int forwardCounter = 0;
        int backwardCounter = 0;
        int length = 0;

        while(forwardCounter != array.length)
        {
            if(array[forwardCounter] == k)
            {
                length++;
                backwardCounter = forwardCounter - 1;
                while(backwardCounter >= 0)
                {
                    if(backwardCounter >= 0 && array[backwardCounter--] < k)
                    {
                        length++;
                    }
                    else
                        break;
                }
            }
            forwardCounter++;
        }
        System.out.println(length);
    }

    public static void main(String[] args) 
    {
        solution(new int[]{4,5,6,4,3,2,4,8,2,4}, 4);
    }

Answer 1

你的解决方案是线性的，但在最坏的情况下你的数组将被遍历两次。最坏的情况显然发生在
-数组按升序排列
-通配符数字是数组的最后一个(即最大的)元素

您的解决方案可以修改为防止向后遍历并仅使用前向遍历的方式。