Python - Độ dài phần đầu nhỏ nhất khi tách mảng 2 phần mọi phần tử part1 ≤ part2

Cho danh sách nums, tách thành part1 (đầu) và part2 (cuối) sao cho mọi phần tử part1 ≤ mọi phần tử part2. Tìm độ dài part1 nhỏ nhất (> 0).

Ví dụ

Input: nums = [3, 1, 2, 5, 4]
Output: 3
Giải thích: part1 = [3, 1, 2], part2 = [5, 4]. Max(part1)=3 ≤ Min(part2)=4.

Thuật toán: Duyệt 1 lần tìm điểm cắt

1. Tìm chỉ số s của phần tử nhỏ nhất đầu tiên
2. p = max(nums[:s+1]) - max của phần đầu đến vị trí min
3. Duyệt từ s+1 đến cuối, nếu gặp phần tử < p thì phải mở rộng part1 đến vị trí đó (cập nhật ans = i)
4. Trả về ans + 1

Mã Python

def solve(nums):
    p = min(nums)
    s = 0
    for i in range(len(nums)):
        if nums[i] == p:
            s = i
            break
    p = max(nums[:s+1])
    ans = s
    for i in range(s+1, len(nums)):
        if nums[i] < p:
            ans = i
    return ans + 1

# Test
nums = [3, 1, 2, 5, 4]
print(solve(nums))  # Output: 3

Giải thích logic

Phần tử nhỏ nhất toàn mảng phải thuộc part1 (vì part2 chỉ chứa phần tử ≥ nó). Vì vậy điểm cắt phải ≥ vị trí min đầu tiên. Sau đó, bất kỳ phần tử nào < max(part1 hiện tại) cũng buộc phải kéo vào part1.

Phân tích độ phức tạp

• Thời gian: O(n)
• Không gian: O(1)

Bài toán liên quan: LeetCode 915 - Partition Array into Disjoint Intervals (yêu cầu part1 không rỗng, part2 không rỗng, max(part1) ≤ min(part2)).