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.

Idea: For each day, find the nearest future day that's warmer. Use a decreasing monotonic stack holding indices of days still awaiting an answer.

Mechanism: scan left→right; when today is warmer than the stack top, pop it and fill the distance i - idx. Each index is pushed and popped exactly once → O(n) despite the nested while.

Picture it: a line of people in decreasing order waiting for a warmer day; whoever sees one leaves the line and records how many days they waited.

function dailyTemperatures(temps: number[]): number[] {
  const res = new Array(temps.length).fill(0)
  const stack: number[] = [] // holds indices
  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
}

Complexity: time O(n), space O(n).

Note: The stack stores indices (not values) so you can compute the distance. This is the "next greater element" template — recognizing it saves a lot of interview time.