739. Daily Temperatures

단조 감소 스택(monotonic decreasing stack)을 사용한다. 스택에 [day, temperature] 쌍을 저장하고, 현재 온도가 스택 top보다 높으면 해당 날의 답을 계산하며 pop한다.

첫번재 풀이에서는 온도를 스택에 함께 저장해주긴 했는데, 사실 temperatures 배열이 원본 그대로 쭉 유지되기 때문에 스택에 인덱스만 저장해주고 온도는 temperatures 배열을 참조해도 괜찮긴 하다.

코드

[day, temperature] 쌍을 저장하는 풀이

function dailyTemperatures(temperatures: number[]): number[] {
  const stack: number[][] = []; // [day, temperature]
  const ans: number[] = new Array(temperatures.length).fill(0);

  for (let day = 0; day < temperatures.length; day++) {
    const temperature = temperatures[day];
    while (stack.length !== 0 && stack[stack.length - 1][1] < temperature) {
      ans[stack[stack.length - 1][0]] = day - stack[stack.length - 1][0];
      stack.pop();
    }
    stack.push([day, temperature]);
  }

  return ans;
}

인덱스만 저장하는 풀이

function dailyTemperatures(temperatures: number[]): number[] {
    const stack: number[] = []; // index only
    const ans = new Array(temperatures.length).fill(0);

    for (let i = 0; i < temperatures.length; i++) {
      while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
        const j = stack[stack.length - 1];
        stack.pop();
        ans[j] = i - j;
      }
      stack.push(i);
    }

    return ans;
  }

시간 / 공간 복잡도

시간 복잡도: O(n) — 각 원소가 스택에 최대 한 번 push/pop
공간 복잡도: O(n) — 스택과 결과 배열

739. Daily Temperatures

문제

풀이

아이디어

코드

시간 / 공간 복잡도