Daily Temperatures: monotonic stack như một cỗ máy trả lời trì hoãn

Bài toán có vẻ đơn giản. Cho một mảng nhiệt độ hàng ngày; với mỗi ngày, trả về số ngày bạn phải chờ đến khi có nhiệt độ cao hơn đúng nghĩa. Nếu không có ngày nào như vậy, trả về 0.

Cách đặt vấn đề này che giấu câu hỏi thực sự: làm thế nào để biết hiệu quả, với mỗi index, vị trí của giá trị lớn hơn gần nhất ở phía trước? Câu trả lời ngây thơ là nhìn về phía trước từng vị trí — đúng nhưng lặp lại mọi phép so sánh. Câu trả lời tốt hơn là đảo ngược quan hệ: thay vì mỗi index đi tìm về phía trước, để index đến sau tự thông báo cho tất cả những ai nó vượt trội hơn. Thông báo đó là một lần pop khỏi stack.

Đề bài

Cho một mảng số nguyên temperatures biểu diễn nhiệt độ hàng ngày, trả về mảng answer trong đó answer[i] là số ngày phải chờ sau ngày i để có nhiệt độ cao hơn; nếu không có ngày nào như vậy, answer[i] bằng 0. Full statement: LeetCode 739.

Ràng buộc:
- 1 <= temperatures.length <= 10^5
- 30 <= temperatures[i] <= 100

Constraints nói gì

Nhiệt độ nằm trong khoảng 30 đến 100. Độ dài mảng lên đến 10^5. Hai con số đó thực hiện hai công việc hoàn toàn khác nhau.

n <= 10^5 loại bỏ O(n²) ngay lập tức. Mười nghìn bình phương là mười tỷ phép so sánh. Với một server phỏng vấn điển hình, đó là khoảng năm giây thời gian chạy thực tế, chính vì vậy bài toán này mới tồn tại. Bất kỳ giải pháp nào lồng vòng lặp qua tất cả các ngày tương lai cho từng ngày hiện tại đều thất bại với constraint này.

Phạm vi nhiệt độ 30 <= temperatures[i] <= 100 hẹp hơn và thú vị hơn. Có đúng 71 nhiệt độ phân biệt. Thay vì một stack tổng quát chứa giá trị tùy ý, bạn có thể theo dõi, với mỗi nhiệt độ có thể, index gần nhất mà nó xuất hiện. Khi đến ngày i với nhiệt độ t, câu trả lời cho i là index tương lai gần nhất trong số tất cả các nhiệt độ t+1 đến 100. Đây là approach dựa trên mảng được mô tả ở cuối, và nó là hệ quả trực tiếp của việc đọc constraint.

Constraint cũng cho bạn biết điều gì đó về các nhiệt độ bằng nhau: temperatures[j] > temperatures[i] là strict, vì vậy hai ngày liên tiếp bằng nhau không được tính. Một index ở lại trong stack cho đến khi có thứ gì đó lớn hơn nghiêm ngặt mới đến.

Approach 1: brute force

Duyệt từng index và scan về phía phải cho đến khi tìm thấy giá trị lớn hơn.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        result = [0] * n
 
        for i in range(n - 1):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    result[i] = j - i
                    break
 
        return result

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        int n = temperatures.Length;
        int[] result = new int[n];
 
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    result[i] = j - i;
                    break;
                }
            }
        }
 
        return result;
    }
}

Index cuối cùng không bao giờ được xử lý bởi vòng ngoài — câu trả lời của nó đã là 0 từ khi khởi tạo.

Time: O(n²). Trường hợp xấu nhất là mảng giảm dần nghiêm ngặt: mỗi index phải scan hết phần còn lại và không bao giờ break sớm.

Space: O(1) auxiliary, không tính mảng đầu ra.

Đây là điểm khởi đầu đúng để suy nghĩ về bài toán, và nó hoàn toàn chính xác. Chỉ là không vượt qua được n = 10^5 trong giới hạn thời gian.

Approach 2: monotonic stack

Insight nằm ở việc đảo ngược ai làm công việc. Trong brute force, mỗi index i hỏi "ai lớn hơn tôi?" Trong approach stack, mỗi index i hỏi ngược lại: "có index nào chưa được giải quyết mà tôi lớn hơn không?" Sự đảo ngược đó cho phép bạn giải quyết nhiều tài khoản còn mở cùng một lúc.

Stack lưu các index của những ngày chưa tìm được ngày ấm hơn. Nó có tính monotonically decreasing về nhiệt độ: nếu nhìn từ đáy lên đỉnh, nhiệt độ chỉ giảm. Invariant đó được duy trì bằng cách pop tất cả những gì bạn vượt trội hơn trước khi push chính mình.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        result = [0] * n
        stack = []  # lưu index; temperatures[stack[-1]] là minimum hiện tại
 
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                prev = stack.pop()
                result[prev] = i - prev
            stack.append(i)
 
        return result

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        int n = temperatures.Length;
        int[] result = new int[n];
        var stack = new Stack<int>();
 
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()]) {
                int prev = stack.Pop();
                result[prev] = i - prev;
            }
            stack.Push(i);
        }
 
        return result;
    }
}

Trace tay: [73, 74, 75, 71, 69, 72, 76, 73]

i=0, temp=73: stack rỗng, push 0         stack=[0]       result=[0,0,0,0,0,0,0,0]
i=1, temp=74: 74>73 -> pop 0, result[0]=1-0=1, push 1   stack=[1]       result=[1,0,0,0,0,0,0,0]
i=2, temp=75: 75>74 -> pop 1, result[1]=2-1=1, push 2   stack=[2]       result=[1,1,0,0,0,0,0,0]
i=3, temp=71: 71<75, push 3              stack=[2,3]     result=[1,1,0,0,0,0,0,0]
i=4, temp=69: 69<71, push 4              stack=[2,3,4]   result=[1,1,0,0,0,0,0,0]
i=5, temp=72: 72>69 -> pop 4, result[4]=5-4=1
              72>71 -> pop 3, result[3]=5-3=2
              72<75, push 5              stack=[2,5]     result=[1,1,0,2,1,0,0,0]
i=6, temp=76: 76>72 -> pop 5, result[5]=6-5=1
              76>75 -> pop 2, result[2]=6-2=4
              push 6                     stack=[6]       result=[1,1,4,2,1,1,0,0]
i=7, temp=73: 73<76, push 7              stack=[6,7]     result=[1,1,4,2,1,1,0,0]

Còn lại trong stack: index 6 và 7, đã khởi tạo là 0.
Kết quả cuối: [1,1,4,2,1,1,0,0]

Khoảnh khắc quan trọng là i=5 (nhiệt độ 72). Trong một lần duyệt qua vòng while, nó giải quyết hai tài khoản còn mở — index 4 (nhiệt độ 69) và index 3 (nhiệt độ 71) — mà không cần xem lại bất kỳ phần tử nào. Brute force sẽ phải lặp lại các phép so sánh đó riêng biệt cho từng index 3 và 4.

Time: O(n). Mỗi index được push đúng một lần và pop nhiều nhất một lần. Tổng số operations: 2n trong trường hợp xấu nhất, vì vậy vòng lặp chạy trong O(n) bất kể có bao nhiêu lần pop xảy ra bên trong while.

Space: O(n). Stack chứa nhiều nhất tất cả n index — điều này xảy ra khi mảng giảm dần nghiêm ngặt và không có gì bị pop cho đến khi toàn bộ mảng được scan xong.

Approach 3: tối ưu bằng mảng với nhiệt độ giới hạn

Gợi ý trong đề bài nói: "nếu nhiệt độ hôm nay là 70, thì trong tương lai nhiệt độ ấm hơn phải là 71, 72, ..., 100. Chúng ta có thể nhớ khi nào tất cả chúng xảy ra tiếp theo." Đó chính xác là điều approach này làm.

Thay vì stack, duy trì một mảng next_warmer kích thước 101 trong đó next_warmer[t] giữ index gần nhất được thấy có nhiệt độ t. Bạn duyệt từ phải sang trái. Với mỗi index i có nhiệt độ t, bạn cần giá trị nhỏ nhất trong số tất cả các entry next_warmer[t+1] đến next_warmer[100]. Giá trị nhỏ nhất đó là ngày tương lai gần nhất ấm hơn.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        result = [0] * n
        next_warmer = [float('inf')] * 101  # next_warmer[t] = index gần nhất với nhiệt độ t
 
        for i in range(n - 1, -1, -1):
            t = temperatures[i]
            # tìm index gần nhất trong số tất cả nhiệt độ ấm hơn
            warmer_idx = min(next_warmer[t + 1:])
            if warmer_idx != float('inf'):
                result[i] = warmer_idx - i
            next_warmer[t] = i  # ghi nhận nhiệt độ t lần cuối xuất hiện tại index i
 
        return result

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        int n = temperatures.Length;
        int[] result = new int[n];
        int[] nextWarmer = new int[101];
        for (int t = 0; t <= 100; t++) nextWarmer[t] = int.MaxValue;
 
        for (int i = n - 1; i >= 0; i--) {
            int t = temperatures[i];
            int warmerIdx = int.MaxValue;
            for (int w = t + 1; w <= 100; w++) {
                if (nextWarmer[w] < warmerIdx) warmerIdx = nextWarmer[w];
            }
            if (warmerIdx != int.MaxValue) result[i] = warmerIdx - i;
            nextWarmer[t] = i;
        }
 
        return result;
    }
}

Time: O(71 * n). Với mỗi trong số n phần tử, bạn scan nhiều nhất 70 entry trong next_warmer (nhiệt độ 101 trừ nhiệt độ hiện tại, nhiều nhất 70). Đây vẫn là O(n) về complexity class — con số 71 là hằng số — nhưng hằng số đó có ý nghĩa trong thực tế.

Space: O(71) = O(1). Mảng next_warmer bị giới hạn bởi phạm vi nhiệt độ, không phải n. Đây là lợi thế thực sự của approach này so với stack: cấu trúc auxiliary không tăng theo kích thước input.

Phân tích edge case

Mảng một phần tử [50]: vòng ngoài trong brute force chạy không lần (range dừng tại n-1 = 0). Approach stack push index 0 rồi kết thúc; không có gì bị pop. Approach mảng tính min trên next_warmer[51:] là inf, vì vậy result[0] vẫn là 0. Cả ba đều trả về [0] đúng.

Mảng giảm dần nghiêm ngặt [90, 80, 70, 60]: brute force làm nhiều nhất — vòng trong không bao giờ break sớm và chạy 3 + 2 + 1 = 6 phép so sánh. Stack tích lũy cả bốn index và không có gì bị pop. Kết quả là [0, 0, 0, 0]. Approach mảng cũng tương tự không tìm được ngày ấm hơn cho bất kỳ index nào.

Mảng tăng dần nghiêm ngặt [30, 40, 50, 60]: vòng trong của brute force luôn break sau một bước. Stack pop index trước ngay lập tức mỗi lần — nó không bao giờ lớn hơn kích thước 1. Approach mảng tìm thấy người hàng xóm ngay bên phải cho mỗi index. Kết quả: [1, 1, 1, 0].

Nhiệt độ bằng nhau kề nhau [70, 70, 71]: điều kiện là temperatures[i] > temperatures[stack[-1]], strict. Index 0 (temp 70) được push; index 1 (temp 70) không trigger pop vì 70 > 70 là false. Cả 0 và 1 đều trong stack khi index 2 (temp 71) đến. Pop index 1: result[1] = 2 - 1 = 1. Pop index 0: result[0] = 2 - 0 = 2. Kết quả: [2, 1, 0]. Bất đẳng thức strict là điều quyết định.

Tất cả nhiệt độ giống nhau [75, 75, 75]: không phần tử nào trigger pop. Stack kết thúc với cả ba index. Kết quả: [0, 0, 0].

Bảng so sánh

Approach bounded-array về mặt kỹ thuật chạy trong O(1) space và O(n) time, nghe có vẻ tối ưu. Trong thực tế, nó xử lý 71 phép so sánh mỗi phần tử so với trung bình được phân bổ khoảng 2 lần mỗi phần tử cho stack. Với n = 10^5, stack thực hiện khoảng 200.000 operations tổng cộng; bounded array thực hiện 7.100.000. Stack thắng về tốc độ thực tế mặc dù cùng O-class.

Pattern cơ bản và tôi sẽ ship gì

Đây là pattern "next greater element" kinh điển: tìm, với mỗi index, index tương lai gần nhất mà giá trị lớn hơn nghiêm ngặt. Monotonic decreasing stack giải quyết toàn bộ họ bài toán này. Insight chính — xuất hiện trong Problems 496, 503, 901 và nhiều bài khác — là bạn lưu index của các phần tử chưa được giải quyết trong stack, không phải bản thân các giá trị. Khi một phần tử mới đến, nó giải quyết tất cả những gì nó vượt trội hơn trong một vòng while duy nhất.

Tôi sẽ ship monotonic stack. Nó là O(n) về cả time và space, code ngắn gọn và dễ đọc, và ánh xạ trực tiếp vào cấu trúc của bài toán: mỗi ngày chờ trong stack cho đến khi được giải quyết. Approach bounded-array đáng biết vì nó chứng minh constraint nhiệt độ có thể khai thác được, nhưng trong bất kỳ setting thực tế nào, overhead 71 lần khiến nó chậm hơn trong thực tế.

Brute force là câu trả lời đầu tiên đúng đắn để đưa ra trong phỏng vấn trước khi tối ưu. Nêu ra nó rồi giải thích tại sao nó thất bại với constraint tốt hơn là nhảy thẳng vào stack.

Vị trí trong series stack và những gì đến tiếp theo

Daily Temperatures là biểu hiện rõ ràng nhất của pattern monotonic stack. Nó loại bỏ mọi phức tạp — không có circular wraparound, không có merge hai mảng, không có tính span — và chỉ để lại phần cốt lõi: một stack của các index đang chờ được giải quyết bởi các giá trị đến sau lớn hơn.

Next Greater Element I (496) là bài khởi động đơn giản hơn. Cho hai mảng, tìm next greater element trong mảng thứ hai cho mỗi phần tử trong mảng thứ nhất. Logic stack hoàn toàn giống nhau; bước thêm là xây dựng một hash map từ giá trị sang câu trả lời. Bài tốt để thử trước bài này.

Next Greater Element II (503) thêm một twist: mảng là circular, vì vậy bạn có thể cần wrap-around. Thủ thuật tiêu chuẩn là duyệt 2n lần với index i % n. Mọi thứ khác vẫn như cũ.

Online Stock Span (901) hỏi: với mỗi giá cổ phiếu đến, có bao nhiêu ngày liên tiếp nhìn về phía sau có giá <= hôm nay? Đây là bài tương tự nhìn ngược. Monotonic decreasing stack lại được dùng, nhưng mỗi entry mang thêm một count, và khi bạn pop bạn tích lũy các span.

Largest Rectangle in Histogram (84) dùng monotonic increasing stack để tìm, với mỗi thanh, thanh ngắn hơn gần nhất ở mỗi bên. Logic stack chạy hai lần (một lần trái-sang-phải, một lần phải-sang-trái, hoặc kết hợp trong một lần duyệt). Nếu Daily Temperatures cảm thấy thoải mái, Histogram là bước leo thang khó hơn để kiểm tra xem bạn có thực sự nắm vững pattern không.