Chương trình phân chia mảng thành các khoảng rời rạc trong Python

Mô tả bài toán

Cho mảng nums. Phân chia thành hai mảng con left và right sao cho:

• Mọi phần tử trong left <= mọi phần tử trong right.
• Cả hai đều không rỗng.
• left có kích thước nhỏ nhất có thể.

Trả về độ dài của left.

Ví dụ

Nếu nums = [5,0,3,8,6], đầu ra là 3 với left = [5,0,3], right = [8,6].

Giải thuật

1. Khởi tạo mx = None, temp = None, nmx = None, temp2 = 0.
2. Duyệt từng phần tử i trong nums:
   • Nếu mx is None: khởi tạo mx = nmx = i, temp = temp2, temp2 += 1.
   • Nếu i >= mx: temp2 += 1, cập nhật nmx nếu cần.
   • Ngược lại: temp = temp2, temp2 += 1, mx = nmx.
3. Trả về temp + 1.

Triển khai Python

def solve(nums):
    mx = None
    temp = None
    nmx = None
    temp2 = 0
    for i in nums:
        if mx is None:
            mx = i
            nmx = i
            temp = temp2
            temp2 += 1
            continue
        if i >= mx:
            temp2 += 1
            if i > nmx:
                nmx = i
            continue
        else:
            temp = temp2
            temp2 += 1
            mx = nmx
            continue
    return temp + 1

nums = [5, 0, 3, 8, 6]
print(solve(nums))

Đầu vào

[5,0,3,8,6]

Đầu ra

3