algorithm - 查找 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;
    }