Daily Temperatures — đợi bao nhiêu ngày mới ấm hơn? Monotonic stack giải thế nào trong O(n)?

Ý tưởng: Với mỗi ngày, tìm ngày gần nhất trong tương lai có nhiệt độ cao hơn. Dùng monotonic stack giảm dần lưu chỉ số các ngày chưa tìm được câu trả lời.

Cơ chế: quét trái→phải, khi ngày hiện tại nóng hơn đỉnh stack thì pop ra và điền khoảng cách i - idx. Mỗi chỉ số được push và pop đúng 1 lần → O(n) dù có vòng while lồng.

Hình dung: một hàng người xếp giảm dần chờ ngày ấm hơn; ai vừa thấy ngày ấm hơn thì rời hàng và ghi lại đã chờ mấy ngày.

function dailyTemperatures(temps: number[]): number[] {
  const res = new Array(temps.length).fill(0)
  const stack: number[] = [] // lưu chỉ số
  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[i] > temps[stack.at(-1)!]) {
      const idx = stack.pop()!
      res[idx] = i - idx
    }
    stack.push(i)
  }
  return res
}

Độ phức tạp: thời gian O(n), bộ nhớ O(n).

Lưu ý: Stack lưu chỉ số (không phải giá trị) để tính được khoảng cách. Đây là khuôn mẫu "next greater element" — nhận ra dạng này tiết kiệm rất nhiều thời gian phỏng vấn.