查找数组分区，其中max（left）<min（right）-可能在O（N）时间内？

Question

我刚刚尝试过编写代码的挑战，以编写一个函数，该函数返回数字数组的最短左侧分区的长度，其所有元素都小于相应右侧分区中的所有元素。

给出的方案是在给定每月温度读数可变的情况下找到“冬季”和“夏季”之间的鸿沟，其规则是所有冬季温度均低于所有夏季温度。我们可以假设至少有一个正确的分区，目标是使冬季最短。

是否可以在O（N）时间中执行此操作，即处理时间随温度读数的数量线性增加？我想出的最快解决方案是为每个考虑的最高冬季温度找到最低夏季温度（在右侧分区中的最低温度）：

function shortestWinterLength temps
    maxWinterTemp = -Infinity

    for i from 0 til temps.length
        minSummerTemp = Infinity

        for j from i + 1 til temps.length
            minSummerTemp = Math.min minSummerTemp, temps[j]

        maxWinterTemp = Math.max maxWinterTemp, temps[i]

        if maxWinterTemp < minSummerTemp
            return i + 1

Answer 1

这是 O(n) 时间和 O(1) 空间复杂度的 C++ 代码。

int solution(vector<int> &A) {

        int leftMax = A[0];     //  Max temperature during winter
        int maximum = A[0];     //  Max temperature during the year
        int position = 1;       //  Possible solution

        int n = A.size();

        for(int i = 1; i < n; i++) {
            if (A[i] < leftMax) {
                position = i+1;      // got a new lower value
                leftMax = maximum;
            } else if (A[i] > maximum) {
                maximum = A[i];
            }
        }        
        return position;
    }

Answer 2

问题中提到的计算 min(temps[i+1], ... temps[n]) 的方法效率低下，因为对不同的i值进行了许多类似的比较。

相反，所有的“最小”值都可以通过对数组执行一次遍历来获得，但是从 right 到 left 迭代。

因此，有必要执行从右到左的初始传递，将迄今为止达到的最小值存储在辅助数组中。之后，您可以使用i当前解决方案中的相同循环，但内部循环j将被替换为简单地从刚刚计算的辅助数组中检索“min”。

该解决方案具有 O(n) 复杂度。