Leaders in an Array

+10

Bạn nhận được một mảng số nguyên nums. Một phần tử là phần tử dẫn đầu khi nó lớn hơn hoặc bằng mọi phần tử ở bên phải nó. Phần tử cuối cùng không có phần tử nào ở bên phải, nên nó luôn là phần tử dẫn đầu. Trả về tất cả các phần tử dẫn đầu theo thứ tự xuất hiện từ trái sang phải trong nums.

Hàm

leaders(nums: integer-array) → integer-array

numsinteger-array: mảng số nguyên cần tìm kiếm
Trả vềinteger-array: các phần tử đầu tiên của nums, từ trái sang phải

Ràng buộc

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

Ví dụ

Đầu vào: nums = [12, 5, 9, 3, 6, 2]
Đầu ra: [12, 9, 6, 2]
Giải thích: 2 ở cuối nên đứng đầu. 6 thắng 2 đứng sau nó, 9 thắng 3, 6 và 2, còn 12 thắng tất cả. 5 thua 9 và 3 thua 6, nên đáp án là [12, 9, 6, 2].

Câu hỏi mở rộng

Nếu các giá trị đến lần lượt và sau mỗi giá trị bạn phải báo cáo những giá trị dẫn đầu cho đến lúc đó, bạn cập nhật danh sách như thế nào để đạt thời gian trung bình O(1) cho mỗi giá trị?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Khi đọc từ trái sang phải, bạn cần quét lại phần hậu tố cho từng phần tử. Thay vào đó, hãy đi từ phải sang trái: điều duy nhất bạn cần biết về phần hậu tố là giá trị lớn nhất của nó, và chỉ cần một biến để lưu giá trị đó. Cách này biến phép kiểm tra O(n²) thành một lượt duyệt duy nhất.

Kiểm tra mọi thứ ở bên phải

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Áp dụng định nghĩa: với mỗi chỉ số i, quét các phần tử phía sau và dừng ở phần tử đầu tiên lớn hơn hẳn nums[i]. Nếu quét đến cuối, nums[i] là phần tử dẫn đầu. Bạn kiểm tra các chỉ số từ trái sang phải, nên các phần tử dẫn đầu xuất hiện theo đúng thứ tự. Trong [12, 5, 9, 3, 6, 2], 5 dừng ở 9 và 3 dừng ở 6.

Chi phí nằm ở những lần quét đến tận cuối. Với 24,999 giá trị bằng nhau rồi đến một giá trị lớn hơn, mỗi phần tử phải quét gần như toàn bộ mảng: khoảng 25,000 × 25,000 / 2, tức hơn 3 × 10^8 phép so sánh.

Thuật toán

Tạo một danh sách kết quả rỗng.
Với mỗi chỉ số i, duyệt j từ i + 1 đến cuối.
Nếu có nums[j] lớn hơn nums[i], dừng lại: nums[i] không phải là phần tử dẫn đầu.
Nếu không có j nào như vậy, thêm nums[i] vào kết quả.
Trả về kết quả.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Một lượt duyệt từ phải sang trái với giá trị lớn nhất hiện tại

Ý tưởng

Phần tử có giá trị lớn ít nhất bằng mọi phần tử ở bên phải tương đương với việc có giá trị lớn ít nhất bằng giá trị lớn nhất trong số đó. Khi duyệt từ phải sang trái, bạn có thể liên tục cập nhật giá trị lớn nhất này. Phần tử cuối cùng là phần tử dẫn đầu và khởi tạo giá trị lớn nhất. Mỗi phần tử ở bên trái sẽ dẫn đầu nếu nó có giá trị lớn ít nhất bằng giá trị lớn nhất hiện tại, rồi trở thành giá trị lớn nhất mới; nếu không, bên phải nó có một giá trị lớn hơn.

Với [12, 5, 9, 3, 6, 2]: 2 dẫn đầu, rồi đến 6, rồi 9, rồi 12, còn 3 và 5 nhỏ hơn giá trị lớn nhất. Bạn tìm được [2, 6, 9, 12]; đảo ngược lại, đó là đáp án.

Mỗi phần tử được so sánh một lần: thời gian O(n) và không gian phụ O(1), ngoài kết quả. Phiên bản R đánh dấu các phần tử dẫn đầu trong một vector logical(n), nên cần không gian phụ O(n).

Thuật toán

Đưa phần tử cuối cùng vào kết quả và đặt best bằng phần tử đó.
Di chuyển i từ chỉ số áp chót xuống 0.
Nếu nums[i] ≥ best, thêm nums[i] vào kết quả và đặt best bằng giá trị đó.
Đảo ngược kết quả để các phần tử dẫn đầu theo thứ tự từ trái sang phải, rồi trả về kết quả.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Lỗi thường gặp và trường hợp biên

Dùng > thay vì ≥ khi so sánh với giá trị lớn nhất hiện tại. Trong [4, 7, 7, 1, 7], mọi số 7 đều là phần tử dẫn đầu, nhưng phép so sánh nghiêm ngặt chỉ giữ lại số cuối cùng.
Bắt đầu giá trị lớn nhất bằng 0 thay vì phần tử cuối cùng. [-1, -5] phải trả về cả hai phần tử, nhưng giá trị lớn nhất là 0 sẽ loại chúng.
Trả về các phần tử dẫn đầu theo thứ tự tìm thấy, [2, 6, 9, 12] thay vì [12, 9, 6, 2].
Thêm phần tử cuối cùng hai lần bằng cách bắt đầu vòng lặp ở chỉ số cuối cùng sau khi đã thêm phần tử đó vào kết quả.
Chỉ so sánh mỗi phần tử với phần tử bên cạnh. Trong [5, 3, 9], số 5 lớn hơn số 3 bên cạnh, nhưng số 9 khiến đáp án là [9].

Câu hỏi thường gặp3

Độ phức tạp thời gian để tìm các phần tử dẫn đầu trong một mảng là bao nhiêu?

O(n) với một lần duyệt từ phải sang trái, vì mỗi phần tử được so sánh một lần với giá trị lớn nhất hiện tại. Việc kiểm tra từng phần tử với mọi phần tử nằm bên phải nó có độ phức tạp O(n²) trong trường hợp xấu nhất, chẳng hạn khi tất cả giá trị đều bằng nhau.

Phần tử cuối cùng có phải lúc nào cũng là người dẫn đầu không?

Đúng. Một phần tử đứng đầu phải lớn hơn hoặc bằng mọi phần tử ở bên phải nó. Phần tử cuối cùng không có phần tử nào ở bên phải, nên điều kiện này đúng mà không cần kiểm tra gì.

Giá trị bằng nhau có được tính là phần tử dẫn đầu không?

Ở đây thì có: một giá trị dẫn đầu phải lớn hơn hoặc bằng mọi phần tử ở bên phải nó, vì vậy trong [4, 7, 7, 1, 7], cả ba số 7 đều dẫn đầu. Một số phiên bản yêu cầu giá trị phải lớn hơn hẳn; khi đó hãy so sánh bằng >, và chỉ giá trị cuối cùng trong các giá trị bằng nhau mới dẫn đầu.

def leaders(nums):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [12, 5, 9, 3, 6, 2]

Đầu ra mong đợi

[12, 9, 6, 2]