Задача: 915. Partition Array into Disjoint Intervals
Сложность: medium

Задав целочисленный массив nums, разбейте его на два (смежных) подмассива left и right так, чтобы: каждый элемент left был меньше или равен каждому элементу right. left и right были непустыми. left имел наименьший возможный размер. Верните длину left после такого разбиения. Тестовые примеры генерируются такие, что разбиение существует.

Пример:

Input: nums = [5,0,3,8,6]
Output: 3

👨‍💻 Алгоритм:

1⃣Создать массив max_left и min_right.

2⃣Заполнить max_left максимальными значениями от начала массива до текущего индекса.
Заполнить min_right минимальными значениями от текущего индекса до конца массива.

3⃣Найти индекс, где max_left[i] меньше или равен min_right[i + 1].
Вернуть длину левого подмассива.

😎 Решение:

class Solution {
    func partitionDisjoint(_ nums: [Int]) -> Int {
        let n = nums.count
        var maxLeft = [Int](repeating: 0, count: n)
        var minRight = [Int](repeating: 0, count: n)
        
        maxLeft[0] = nums[0]
        for i in 1..<n {
            maxLeft[i] = max(maxLeft[i - 1], nums[i])
        }
        
        minRight[n - 1] = nums[n - 1]
        for i in stride(from: n - 2, through: 0, by: -1) {
            minRight[i] = min(minRight[i + 1], nums[i])
        }
        
        for i in 0..<n - 1 {
            if maxLeft[i] <= minRight[i + 1] {
                return i + 1
            }
        }
        return n
    }
}

Ставь 👍 и забирай 📚 Базу знаний