739. Daily Temperatures
Tags:
Medium
Skills:
Monotonic stack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Cho một mảng số nguyên temperatures, mỗi phần tử là nhiệt độ hàng ngày. Với mỗi ngày, bạn cần trả lời: sau bao nhiêu ngày nữa thì nhiệt độ sẽ cao hơn ngày hiện tại? Nếu không có ngày nào như vậy, trả về 0 cho ngày đó.
Bài này có thể giải bằng cash duyệt ngược mảng và sử dụng một stack để lưu chỉ số các ngày mà nhiệt độ chưa tìm được ngày nóng hơn
Solution
1function dailyTemperatures(temps: number[]): number[] {
2 const n = temps.length;
3 const ans = new Array(n).fill(0);
4 const stack: number[] = [];
5
6 for(let i = n - 1; i >= 0; i--) {
7 while(stack.length > 0 && temps[i] >= temps[stack.at(-1)]) {
8 stack.pop()
9 }
10 if(stack.length > 0) {
11 ans[i] = stack.at(-1) - i;
12 }
13
14 stack.push(i)
15 }
16
17 return ans;
18};