Next Greater Element I

Q: Độ phức tạp thời gian của Next Greater Element I là gì?

Lời giải dùng ngăn xếp đơn điệu chạy trong thời gian O(n + m) , trong đó n là độ dài của nums2 và m là độ dài của nums1 , đồng thời dùng O(n) không gian cho bản đồ và ngăn xếp. Quét sang phải từ mỗi giá trị mất thời gian O(n·m) .

DễNgăn xếp đơn điệu Băm

+10

Bạn nhận được hai mảng số nguyên phân biệt, nums1 và nums2, và mọi giá trị trong nums1 đều xuất hiện trong nums2. Phần tử lớn hơn tiếp theo của một giá trị x là giá trị đầu tiên nằm bên phải x trong nums2 và lớn hơn x, hoặc là -1 nếu không có giá trị nào như vậy.

Trả về một mảng chứa phần tử lớn hơn tiếp theo của mỗi giá trị trong nums1, theo thứ tự của nums1.

Hàm

nextGreaterElement(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: các giá trị cần tìm, tất cả đều có trong nums2
nums2integer-array: mảng mà bạn tìm kiếm ở bên phải mỗi giá trị
Trả vềinteger-array: phần tử lớn hơn tiếp theo của mỗi giá trị trong nums1, hoặc -1, theo thứ tự của nums1

Ràng buộc

1 ≤ nums1.length ≤ nums2.length ≤ 10⁴
0 ≤ nums1[i], nums2[i] ≤ 10⁴
Tất cả giá trị trong nums1 đều khác nhau, và tất cả giá trị trong nums2 đều khác nhau.
Mọi giá trị trong nums1 đều xuất hiện trong nums2.

Ví dụ

Đầu vào: nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
Đầu ra: [8, -1, 6]
Giải thích: Sau số 3 trong nums2 là 8 và 2, trong đó 8 là số lớn hơn đầu tiên. Chỉ có 2 đứng sau số 8, nên 8 nhận giá trị -1. Ngay sau số 1 là 6, vốn đã lớn hơn.

Đầu vào: nums1 = [5, 2]nums2 = [2, 9, 5, 4]
Đầu ra: [-1, 9]
Giải thích: Chỉ có 4 đứng sau 5 và nhỏ hơn, nên 5 nhận -1. Ngay sau 2 là 9. Các đáp án theo thứ tự của nums1.

Câu hỏi mở rộng

Với mỗi vị trí trong nums2, bạn có thể trả về số bước sang phải để đến phần tử lớn hơn tiếp theo của nó chỉ với một lượt duyệt không?

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

Quét sang phải từ mỗi giá trị trong nums1 khiến bạn phải lặp lại công việc, trong khi các câu trả lời chỉ phụ thuộc vào nums2. Chỉ cần duyệt một lần với ngăn xếp đơn điệu là có thể tìm phần tử lớn hơn kế tiếp của mọi giá trị trong nums2 cùng lúc. Bản đồ băm lưu các phần tử đó, rồi tra cứu để tìm câu trả lời cho nums1.

Tìm từng giá trị và quét sang phải

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

Ý tưởng

Với mỗi giá trị x trong nums1, hãy tìm x trong nums2 rồi quét sang phải đến giá trị đầu tiên lớn hơn, hoặc đến cuối mảng nếu không có, khi đó kết quả là -1. Lần quét lần lượt đi qua các giá trị nằm bên phải x, vì vậy giá trị lớn hơn đầu tiên mà nó gặp chính là đáp án.

Nếu nums2 giảm dần, mỗi lần quét đều đi đến cuối mảng: tối đa m × n bước, tức là 10^8 bước khi cả hai mảng đều có 10^4 giá trị.

Thuật toán

Duyệt qua từng giá trị x trong nums1.
Tìm chỉ số j sao cho nums2[j] bằng x.
Duyệt nums2 từ j+1 và dừng ở giá trị đầu tiên lớn hơn x.
Thêm giá trị đó vào danh sách, hoặc thêm -1 nếu đã duyệt đến cuối danh sách.
Trả về các đáp án đã thu thập.

def nextGreaterElement(nums1, nums2):
    result = []
    for x in nums1:
        j = 0
        while nums2[j] != x:
            j += 1
        answer = -1
        for k in range(j + 1, len(nums2)):
            if nums2[k] > x:
                answer = nums2[k]
                break
        result.append(answer)
    return result

Ngăn xếp đơn điệu và bảng băm

Ý tưởng

Duyệt nums2 một lần và để mỗi giá trị mới trả lời cho những giá trị trước đó mà nó lớn hơn. Giữ các giá trị đang chờ câu trả lời trên một ngăn xếp. Khi một giá trị xuất hiện, lấy khỏi đỉnh ngăn xếp mọi giá trị nhỏ hơn và ánh xạ chúng đến giá trị mới, tức giá trị lớn hơn đầu tiên ở bên phải. Sau đó, đẩy giá trị mới vào ngăn xếp.

Ngăn xếp giảm dần từ đáy lên đỉnh, vì chỉ đẩy một giá trị vào sau khi đã lấy khỏi ngăn xếp mọi giá trị nhỏ hơn nằm phía trên nó, nên bạn chỉ cần xem đỉnh ngăn xếp. Một giá trị rời khỏi ngăn xếp ngay khi giá trị lớn hơn đầu tiên xuất hiện, nên câu trả lời của nó là giá trị lớn hơn đầu tiên, không phải giá trị lớn nhất.

Với [1, 6, 3, 8, 2], 6 lấy 1 khỏi ngăn xếp, sau đó 8 lấy 3 và 6, còn 8 và 2 kết thúc mà không có câu trả lời. Mỗi giá trị được đẩy vào một lần và lấy khỏi ngăn xếp tối đa một lần, nên với m lần tra cứu, thời gian là O(n + m).

Thuật toán

Tạo một bản đồ rỗng và một ngăn xếp rỗng.
Với mỗi giá trị trong nums2, lấy ra khỏi đỉnh ngăn xếp mọi giá trị nhỏ hơn rồi ánh xạ chúng tới giá trị hiện tại.
Đẩy giá trị hiện tại vào ngăn xếp.
Với mỗi giá trị trong nums1, trả về câu trả lời đã ánh xạ của nó hoặc -1 nếu không có.

def nextGreaterElement(nums1, nums2):
    next_greater = {}
    stack = []  # values still waiting for a greater one, decreasing from bottom to top
    for value in nums2:
        # value is the first greater value to the right of every smaller value on the stack.
        while stack and stack[-1] < value:
            next_greater[stack.pop()] = value
        stack.append(value)
    # Whatever is still on the stack has no greater value to its right.
    return [next_greater.get(x, -1) for x in nums1]

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

Ghi lại giá trị lớn nhất ở bên phải thay vì giá trị lớn hơn đầu tiên. Trong nums2 = [3, 5, 1, 2, 4, 9, 0], đáp án cho 1 là 2, không phải 9.
Trả về đáp án theo thứ tự của nums2. Kết quả có một phần tử cho mỗi giá trị của nums1, theo thứ tự của chúng: [-1, 9] trong ví dụ thứ hai.
Đọc nums2 tại chỉ số của một giá trị trong nums1. Trong ví dụ đầu tiên, 3 nằm ở chỉ số 0 trong nums1 nhưng ở chỉ số 2 trong nums2.
Quên các giá trị còn lại trên ngăn xếp. Đáp án của chúng là -1, và thao tác tra cứu trong map không có giá trị mặc định sẽ thất bại.

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

Độ phức tạp thời gian của Next Greater Element I là gì?

Lời giải dùng ngăn xếp đơn điệu chạy trong thời gian O(n + m), trong đó n là độ dài của nums2 và m là độ dài của nums1, đồng thời dùng O(n) không gian cho bản đồ và ngăn xếp. Quét sang phải từ mỗi giá trị mất thời gian O(n·m).

Ngăn xếp đơn điệu là gì?

Một ngăn xếp có các giá trị được sắp xếp từ dưới lên trên. Trước khi đẩy một giá trị vào, bạn lấy ra mọi giá trị có thể phá vỡ thứ tự, và mỗi lần lấy ra là lúc bạn tìm được một đáp án. Cách này giải quyết các bài toán tìm giá trị lớn hơn tiếp theo, nhỏ hơn tiếp theo và các bài toán tương tự trong thời gian tuyến tính.

Vì sao Next Greater Element I cần bảng băm?

Quá trình duyệt ngăn xếp tạo ra các đáp án gắn với giá trị trong nums2, theo thứ tự chúng rời khỏi ngăn xếp. Đầu ra tuân theo thứ tự của nums1, trong đó các giá trị giống nhau nằm ở những vị trí khác. Tất cả giá trị đều khác nhau, nên ánh xạ từ giá trị sang đáp án liên kết hai mảng bằng một lần tra cứu có thời gian hằng số cho mỗi mảng.

Điều gì thay đổi nếu nums2 là mảng vòng tròn?

Việc tìm giá trị lớn hơn có thể tiếp tục từ đầu mảng. Chạy cùng một lượt duyệt ngăn xếp hai lần, với chỉ số i % n cho i từ 0 đến 2n-1, và chỉ đẩy giá trị vào ngăn xếp ở lượt đầu tiên. Những giá trị vẫn còn trên ngăn xếp sau cả hai lượt không có giá trị nào lớn hơn ở bất kỳ vị trí nào, vì vậy đáp án của chúng là -1.

def nextGreaterElement(nums1, nums2):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums1 = [3, 8, 1]
nums2 = [1, 6, 3, 8, 2]

Đầu ra mong đợi

[8, -1, 6]