Daily Temperatures

Description

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution(javascript)

// // O(n^2) time O(n) space
// const dailyTemperatures = (T = []) => {
//   const result = []
//   const find = (index) => {
//     for (let i = index; i < T.length; i++) {
//       if (T[i] > T[index]) {
//         return i - index
//       }
//     }
//     return 0
//   }
//   for (let i = 0; i < T.length; i++) {
//     result[i] = find(i)
//   }
//   return result
// }

// O(n) time O(n) space
const dailyTemperatures = (T = []) => {
  const stack = []
  const result = new Array(T.length).fill(0)
  for (let i = 0; i < T.length; i++) {
    while (T[i] > T[stack[stack.length - 1]] && stack.length > 0) {
      const index = stack.pop()
      result[index] = i - index
    }
    stack.push(i)
  }
  return result
}