LeetCode 739 - Daily Temperatures (Medium)

문제

LeetCode - 739번

풀이 과정

각 날의 온도 정보가 배열로 주어질 때 각 날의 온도를 기준으로 기온이 상승하는 최초의 날을 찾는 문제입니다.

브루트 포스 를 사용해서 모든 경우를 따질 경우 O(N^2) 의 시간 복잡도로 시도해볼 수 있겠지만
입력 값의 크기 때문에 시간 초과가 발생합니다. 대신에 스택 을 사용하면 O(N) 에 이 문제를 해결할 수 있습니다.

스택 에 각 날짜의 온도를 인덱스와 함께 저장하며 만약 새로 들어오는 날짜의 온도가 top 보다 높을 경우에는
해당 날짜보다 온도가 높은 날이 남을때까지 pop 해주며 날짜 간격을 계산합니다.

만약 최종적으로 스택 이 비어있지 않다면 남아있는 온도는 모두 내림차순으로 되어 있는 것이므로 0 으로 해주면 되는 것입니다.

코드

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function (T) {
  const stack = [];
  const answer = [];

  for (let i = 0; i < T.length; i++) {
    if (!stack.length || top(stack) >= T[i]) {
      stack.push([T[i], i]);
    } else {
      while (stack.length > 0 && top(stack)[0] < T[i]) {
        answer[top(stack)[1]] = i - top(stack)[1];
        stack.pop();
      }
      stack.push([T[i], i]);
    }
  }

  if (stack.length) {
    stack.forEach((s) => (answer[s[1]] = 0));
  }

  return answer;
};

function top(stack) {
  return stack[stack.length - 1];
}