Daily Temperatures

Q: Độ phức tạp thời gian của Daily Temperatures là gì?

Lời giải dùng ngăn xếp đơn điệu chạy trong O(n) thời gian và dùng thêm O(n) bộ nhớ, vì mỗi ngày được đưa vào ngăn xếp một lần và bị lấy ra nhiều nhất một lần. Quét về phía trước từ mỗi ngày mất O(n²) thời gian, tương đương khoảng 5 × 10^7 phép so sánh cho 10^4 ngày không có ngày nào ấm hơn.

Q: Có thể giải bài Nhiệt độ hằng ngày mà không cần ngăn xếp không?

Có. Điền đáp án từ ngày cuối cùng trở về trước, với ngày i , bắt đầu từ j = i+1 ; khi ngày j chưa ấm hơn, chuyển đến j + answer[j] , tức ngày trả lời cho j . Nếu answer[j] là 0, ngày i cũng nhận giá trị 0. Các bước nhảy bỏ qua những ngày không thể trả lời cho i : thời gian O(n) , không cần thêm bộ nhớ.

Trung bìnhNgăn xếp đơn điệu

+10

temperatures[i] là nhiệt độ vào ngày i. Với mỗi ngày, hãy đếm số ngày bạn phải chờ sau ngày đó cho đến khi nhiệt độ cao hơn xuất hiện, hoặc trả về 0 nếu sau đó không có ngày nào ấm hơn. Trả về một mảng có cùng độ dài, trong đó phần tử i là số ngày chờ của ngày i.

Hàm

dailyTemperatures(temperatures: integer-array) → integer-array

temperaturesinteger-array: nhiệt độ của từng ngày, theo thứ tự
Trả vềinteger-array: cho mỗi ngày, số ngày còn lại cho đến ngày có nhiệt độ cao hơn, hoặc 0 nếu không có ngày nào như vậy

Ràng buộc

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Nhiệt độ ấm hơn nghĩa là phải cao hơn hẳn: ngày sau có cùng nhiệt độ thì không được tính.

Ví dụ

Đầu vào: temperatures = [71, 69, 72, 70, 70, 75, 68]
Đầu ra: [2, 1, 3, 2, 1, 0, 0]
Giải thích: Ngày 0 (71) chờ 2 ngày để gặp 72. Ngày 3 (70) bỏ qua giá trị 70 bằng nhau vào ngày 4 và chờ 2 ngày để gặp 75. Không có ngày nào sau 75 hoặc 68 ấm hơn, nên cả hai đều nhận 0.

Câu hỏi mở rộng

Nhiệt độ chỉ nhận 71 giá trị, từ 30 đến 100. Làm thế nào một bảng được đánh chỉ số theo nhiệt độ có thể trả lời trong một lượt cho mọi ngày, từ phải sang trái, và với cái giá nào?

Lời giải

Quét tiến từ mỗi ngày sẽ lặp lại công việc, và khi những ngày ấm áp hiếm hoi thì mỗi lần quét đều chạy đến cuối. Thay vào đó, hãy đi qua các ngày một lần và để mỗi ngày mới trả lời những ngày trước đó mà nó nóng hơn. Những ngày vẫn đang chờ nằm trên một ngăn xếp có nhiệt độ không bao giờ tăng từ dưới lên trên, vì vậy mọi câu trả lời đều có được chỉ trong một lượt.

Quét tiến lên từ mỗi ngày

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

Ý tưởng

Với ngày i, hãy kiểm tra các ngày i+1, i+2 rồi tiếp tục như vậy, và dừng ở ngày đầu tiên j có nhiệt độ cao hơn hẳn. Đáp án là j-i, hoặc 0 nếu quá trình quét đến cuối. Quét theo thứ tự đảm bảo ngày đầu tiên có nhiệt độ cao hơn mà bạn gặp cũng là ngày đầu tiên có nhiệt độ cao hơn.

Nếu cả 10^4 ngày đều có cùng nhiệt độ, quá trình quét sẽ không dừng sớm: khoảng n²/2 = 5 × 10^7 phép so sánh, và ngày 1 đi qua gần như cùng quãng đường mà ngày 0 đã đi qua.

Thuật toán

Tạo một mảng kết quả gồm các số 0, mỗi phần tử ứng với một ngày.
Với mỗi ngày i, quét j từ i+1 đến ngày cuối cùng.
Tại j đầu tiên thỏa mãn temperatures[j] > temperatures[i], lưu j-i rồi dừng quét.
Trả về mảng kết quả; những ngày không tìm thấy kết quả khi quét sẽ giữ giá trị 0.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # the first warmer day, so stop here
                break
    return answer

Ngăn xếp đơn điệu lưu số ngày chờ

Ý tưởng

Hãy lưu những ngày chưa có câu trả lời vào một ngăn xếp dưới dạng chỉ số. Khi đến ngày hôm nay, hãy lấy ra từng ngày đang chờ có nhiệt độ thấp hơn hôm nay: hôm nay là ngày đầu tiên ấm hơn, nên câu trả lời là today - day. Sau đó, đưa hôm nay vào ngăn xếp.

Chỉ cần kiểm tra phần tử trên cùng. Một ngày chỉ được đưa vào ngăn xếp sau khi mọi ngày lạnh hơn nằm phía trên nó đã được lấy ra, nên nhiệt độ trên ngăn xếp không bao giờ tăng từ dưới lên trên. Nếu hôm nay không ấm hơn phần tử trên cùng, thì hôm nay cũng không ấm hơn bất kỳ ngày nào bên dưới, và bạn dừng lấy phần tử ra. Trong ví dụ đầu tiên, ngày 5 (75) lấy các ngày 4, 3 và 2 ra, với thời gian chờ lần lượt là 1, 2 và 3, trong khi ngày 70 thứ hai không lấy ngày đầu tiên ra, vì nhiệt độ bằng nhau không được xem là ấm hơn.

Mỗi ngày được đưa vào ngăn xếp một lần và được lấy ra nhiều nhất một lần, nên tổng số lần lấy ra không vượt quá n: độ phức tạp thời gian O(n), dù một ngày có thể lấy ra nhiều ngày.

Thuật toán

Tạo một mảng kết quả gồm các số 0 và một ngăn xếp chỉ số rỗng.
Với mỗi ngày today, khi ngày ở đầu ngăn xếp lạnh hơn hôm nay, hãy lấy ngày đó ra khỏi ngăn xếp và đặt kết quả của ngày đó bằng today trừ đi chỉ số của ngày đó.
Đẩy today vào ngăn xếp.
Sau vòng lặp, những ngày còn trong ngăn xếp không có ngày nào ấm hơn và giữ giá trị 0. Trả về mảng kết quả.

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    waiting = []  # indices of days with no warmer day yet, colder toward the top
    for today, temp in enumerate(temperatures):
        # Today is the first warmer day for every colder day on top of the stack.
        while waiting and temperatures[waiting[-1]] < temp:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    # Days still waiting never get a warmer day and keep their 0.
    return answer

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

Lấy ra khi dùng >= thay vì >. Trong ví dụ đầu tiên, ngày 3 sau đó chờ 1 ngày để gặp mức nhiệt 70 thứ hai, thay vì 2 ngày để gặp mức nhiệt 75.
Đẩy nhiệt độ vào ngăn xếp thay vì chỉ số. Khi đó, bạn không thể tính khoảng cách hoặc biết cần điền vào mục nào trong đáp án.
Dùng if khi bạn cần while. Một ngày nóng có thể trả lời cho nhiều ngày đang chờ: mức nhiệt 75 trong ví dụ đầu tiên trả lời cho ba ngày.
Để các ngày còn trên ngăn xếp chưa được gán giá trị. Đáp án của chúng là 0; trong C, hãy cấp phát đáp án bằng calloc, vì vùng nhớ malloc chứa dữ liệu rác.
Để lượt duyệt xuôi chạy qua ngày đầu tiên có nhiệt độ cao hơn. Nếu không có break, chương trình sẽ ghi nhận ngày cuối cùng có nhiệt độ cao hơn.

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

Độ phức tạp thời gian của Daily Temperatures là gì?

Lời giải dùng ngăn xếp đơn điệu chạy trong O(n) thời gian và dùng thêm O(n) bộ nhớ, vì mỗi ngày được đưa vào ngăn xếp một lần và bị lấy ra nhiều nhất một lần. Quét về phía trước từ mỗi ngày mất O(n²) thời gian, tương đương khoảng 5 × 10^7 phép so sánh cho 10^4 ngày không có ngày nào ấm hơn.

Có thể giải bài Nhiệt độ hằng ngày mà không cần ngăn xếp không?

Có. Điền đáp án từ ngày cuối cùng trở về trước, với ngày i, bắt đầu từ j = i+1; khi ngày j chưa ấm hơn, chuyển đến j + answer[j], tức ngày trả lời cho j. Nếu answer[j] là 0, ngày i cũng nhận giá trị 0. Các bước nhảy bỏ qua những ngày không thể trả lời cho i: thời gian O(n), không cần thêm bộ nhớ.

Daily Temperatures liên quan như thế nào đến Next Greater Element?

Ở mỗi vị trí, ta đều đặt cùng một câu hỏi: tìm giá trị lớn hơn tiếp theo ở bên phải. Next Greater Element trả về giá trị đó; Daily Temperatures trả về khoảng cách đến giá trị đó, vì vậy ngăn xếp lưu các chỉ số. Dùng cùng ngăn xếp nhưng đổi điều kiện để lấy phần tử nhỏ hơn ra, ta có thể tìm phần tử nhỏ hơn tiếp theo.

def dailyTemperatures(temperatures):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

temperatures = [71, 69, 72, 70, 70, 75, 68]

Đầu ra mong đợi

[2, 1, 3, 2, 1, 0, 0]