739. Daily Temperatures

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/daily-temperatures/description/

Table of Contents

1. Cách tiếp cận vấn đề

Bài toán cho một mảng các số nguyên đại diện cho nhiệt độ hằng ngày được ghi nhận lại và yêu cầu chúng ta trả về một mảng output với từng phần tử đại diện số ngày cần đợi để đạt được nhiệt độ cao hơn tương ứng với từng nhiệt độ từng trong mảng input (nếu không có ngày nào thì bằng 0). Ví dụ:

• Input: temperatures = [73,74,75,71,69,72,76,73]
• Output: [1,1,4,2,1,1,0,0]

Explain: 73 và 74 cần 1 ngày để có nhiệt độ cao hơn, trong khi 75 cần 4 ngày để đạt nhiệt độ cao hơn là 76. Ta thấy 2 số 0 trong mảng kết quả là do số 76 là max và số 73 thì là phần tử cuối cùng của mảng nên không thể có phần tử nào có gía trị cao hơn nằm phía sau được.

Cách tiếp cận ngây thơ nhất là sử dụng BruteForce với 2 vòng lặp, cố định từng phần tử và tìm phần tử có nhiệt độ cao hơn phần tử cố định. Tuy nhiên độ phức tạp của nó sẽ khá lớn O(n^2) đòi hỏi chúng ta phải cải tiến nó.

Chúng ta sẽ thay đổi cách tiếp cận vấn đề một chút, mỗi lần duyệt qua 1 phần tử, thay vì nghĩ xuôi là:

• Ta sẽ cố định phần tử đó và cố gắng tìm phần tử đầu tiên có giá trị lớn hơn nó.

Thì ta sẽ tư duy ngược 1 xíu:

• Ta sẽ cố định phần tử đó và tìm xem trong những phần tử đã duyệt trước đó, có bao nhiêu phần tử nhỏ hơn phần tử đang cố định mà chưa được cập nhật kết quả trong mảng output. Ta sẽ cập nhật kết quả cho những phần tử nhỏ hơn đó bằng cách lấy vị trí của phần tử đang cố định - vị trí của phần tử có giá trị nhỏ hơn.
• Lưu ý là chỉ cập nhật cho những phần tử nhỏ hơn nhưng chưa được cập nhật kết quả trước đó, vì số đang cố định hiện tại có thể không phải là số lớn nhất đầu tiên của nó, có thể nó đã gặp 1 số lớn hơn khác và cập nhật kết quả trước đó rồi. Ví dụ: [1,2,3] thì 3 chỉ có thể cập nhật cho 2 được mà thôi, còn số 1 thì đã được cập nhật bởi số 2 trước đó rồi.

Vậy ta cần tìm 1 cấu trúc dữ liệu phù hợp để đạt được cách tiếp cận đã nêu trên, và nó phải đảm bảo độ phức tạp là O(n), hay nói cách khác là thao tác "lấy ra các phần tử nhỏ hơn phần tử đang cố định mà chưa được cập nhật kết quả trong mảng output" phải đạt độ phức tạp là O(1) do ta đã có 1 vòng for cố định các phần tử trước đó rồi.

2. Solution & Phân Tích

Từ ý tưởng đã nêu, ta có thể suy nghĩ đến việc dùng Stack để lưu trữ lại các vị trí index của nhiệt độ cho đến khi tất cả phần tử trong Stack hiện tại gặp 1 nhiệt độ cao hơn thì sẽ tiến hành pop các phần tử nhỏ hơn nhiệt độ đó ra và cập nhật kết quả - có nghĩa là tất cả giá trị nhiệt độ được lưu trữ trong Stack trước đó sẽ phải có thứ tự giảm dần - Stack mà có tính chất như vậy thì gọi là Monotonic Stack (Stack mà chỉ lưu các phần tử có tính chất đơn điệu: tăng dần hoặc giảm dần). Cụ thể như sau:

Ta sẽ duyệt lần lượt qua các nhiệt độ, với mỗi nhiệt độ x có vị trí là i:

• Ta sẽ dùng 1 vòng lặp while với điều kiện dừng là: temperatures[top] >= temperatures[i] (i là vị trí của x, khi x sẽ không thể lớn hơn bất kỳ phần tử nào hiện tại trong Stack được thì ta dừng lại)
• Mỗi lần ta thấy phần tử top còn < x thì sẽ tiến hành pop ra index của nó, tạm gọi là j
• Cập nhật giá trị trong mảng output[j] = i - j
• Sau khi cập nhật giá trị cho các phần tử nhỏ hơn x, ta sẽ push vị trí của x là i vào trong stack để tiếp tục lặp lại process ở trên. 

Kết thúc vòng lặp, trong Stack sẽ còn lại:

• 1 phần tử max nếu phần tử max đó nằm ở vị trí cuối cùng
• 1 phần tử max và 1 phần tử ở vị trí cuối cùng nếu 2 phần tử đó là khác nhau

Time-Complexity: O(n), mặc dù ta có 1 vòng lặp for để duyệt qua các nhiệt độ, và 1 vòng lặp while cho thao tác get top và pop() trong stack, tuy nhiên các thao tác trong stack chỉ tốn O(1) nên ta có thể rút gọn lại thành O(n).

Space-Complexity: O(n)

Với n là số lượng các phần tử trong mảng temperatures.

3. Code

stack.peek(): xem giá trị top hiện tại của stack.

stack.pop(): lấy ra khỏi stack giá trị ở vị trí top.

stack.push(x): thêm giá trị x vào trong stack, top hiện tại chính là x.

Ta có thể thay thế cấu trúc dữ liệu stack bằng mảng và 1 con trỏ top để simulate lại stack với độ hiệu quả tương đương.

© hieulm2k | Buy me a coffee