Số Ngày Chờ Ấm LênDaily Temperatures
Hiểu bài
Cho mảng temps nhiệt độ từng ngày. Với mỗi ngày, trả về số ngày phải chờ tới khi gặp ngày ấm hơn. Nếu không có ngày nào ấm hơn về sau, ghi 0.
Ví dụ:
temps = [73, 74, 75, 71, 69, 72, 76, 73]
output = [ 1, 1, 4, 2, 1, 1, 0, 0]
// ngày 0 (73°) chờ 1 ngày là gặp 74°; ngày 2 (75°) chờ tới ngày 6 (76°) = 4 ngàyXem cách cơ bản (chậm hơn)
O(n²) time, O(1) spacefunction dailyTemperatures(temps: number[]): number[] {
const res = new Array(temps.length).fill(0)
for (let i = 0; i < temps.length; i++) {
for (let j = i + 1; j < temps.length; j++) {
if (temps[j] > temps[i]) { res[i] = j - i; break }
}
}
return res
}Mỗi ngày quét toàn bộ ngày phía sau để tìm ngày ấm hơn.
Với mảng giảm dần (mỗi ngày phải quét tới cuối), số phép so sánh xấp xỉ n²/2 — chậm khi n lớn.
Lời giải tối ưu
O(n) time, O(n) spacefunction dailyTemperatures(temps: number[]): number[] {
const res = new Array(temps.length).fill(0)
const stack: number[] = [] // chỉ số, nhiệt độ giảm dần từ đáy lên đỉnh
for (let i = 0; i < temps.length; i++) {
while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
const prev = stack.pop()!
res[prev] = i - prev
}
stack.push(i)
}
return res
}Stack đơn điệu (monotonic stack) giữ các chỉ số ngày chưa tìm được ngày ấm hơn, nhiệt độ giảm dần.
- Mỗi ngày mới ấm hơn sẽ "giải quyết" hết các ngày tồn ở đỉnh stack.
- Mỗi chỉ số được đẩy vào và lấy ra đúng 1 lần → tổng cộng O(n).
Chạy thử từng bước
- 1
Hình dung temps = [73, 74, 72, 76]. i=0 (73°): stack rỗng nên không giải quyết được gì, đẩy chỉ số 0 vào. stack giữ chỉ số [0].
i:0temp:73stack:[0]res:[0,0,0,0] - 2
i=1 (74°): 74 > temps[đỉnh=0]=73 → lấy 0 ra, res[0] = 1−0 = 1.
Stack rỗng, đẩy 1 vào.
i:1temp:74popped:0stack:[1]res:[1,0,0,0] - 3
i=2 (72°): 72 > temps[đỉnh=1]=74? Không.
Chưa giải quyết ai, đẩy 2 vào. stack = [1, 2].
i:2temp:72stack:[1,2]res:[1,0,0,0] - 4
i=3 (76°): 76 > 72 → res[2]=3−2=1; 76 > 74 → res[1]=3−1=2.
- Đẩy 3 vào.
- Hết mảng, các chỉ số còn trong stack giữ giá trị 0.
- Kết quả [1, 2, 1, 0].
i:3temp:76popped:[2,1]stack:[3]res:[1,2,1,0]
Trường hợp biên phải nhớ
Mảng giảm dần hẳn ([76, 75, 74]) — không ngày nào ấm hơn về sau, mọi phần tử = 0; stack chỉ chồng lên, không pop.
Hai ngày bằng nhau (temps[j] === temps[i]) — KHÔNG tính là ấm hơn, dùng dấu
>chứ không phải>=, nếu không sẽ trả sai.Mảng tăng dần ([70, 71, 72]) — mỗi ngày giải quyết ngay ngày liền trước, kết quả toàn 1 trừ phần tử cuối.
Mảng 1 phần tử → trả [0].