LeetCode - 739. Daily Temperatures

Thoughts:

I choose monotonic stack to solve this problem.

If I want to find a bigger or smaller number, after or before the current element, this algorithm can help a lots!!!

The complexity will be O(n) because it iterate and compare with the top element of the stack with the current element

Thoughts visuzlization:

temperatures = [73,74,75,71,69,72,76,73]

answer = [0,0,0,0,0,0,0,0]
set every element to zero because I just need to handle the situation
that encounter a bigger number

stack = []
store the index of element in temperatures array
the stack will be a decreasing monotonic stack
when encounter a bigger number, keep popping and checking the top element of the
stack (the smallest one) with the current element, then calculate the
diffrence of those two indice.

[73,74,75,71,69,72,76,73] stack = [0(73)]
  i                       answer = [0,0,0,0,0,0,0,0]

[73,74,75,71,69,72,76,73] 1(74) - 0(73) = 1
     i                    stack = [1(74)]
                          answer = [1,0,0,0,0,0,0,0]

[73,74,75,71,69,72,76,73] 2(75) - 1(74) = 1
        i                 stack = [2(75)]
                          answer = [1,1,0,0,0,0,0,0]

[73,74,75,71,69,72,76,73] stack = [2(75),3(71)]
           i              answer = [1,1,0,0,0,0,0,0]

[73,74,75,71,69,72,76,73] stack = [2(75),3(71),4(69)]
              i           answer = [1,1,0,0,0,0,0,0]

[73,74,75,71,69,72,76,73] 5(72) - 4(69) = 1
                 i        stack = [2(75),3(71)]
                          answer = [1,1,0,0,1,0,0,0]

[73,74,75,71,69,72,76,73] 5(72) - 3(61) = 2
                 i        stack = [2(75)]
                          answer = [1,1,0,2,1,0,0,0]

[73,74,75,71,69,72,76,73] stack = [2(75),5(72)]
                 i        answer = [1,1,0,2,1,0,0,0]

[73,74,75,71,69,72,76,73] 6(76) - 5(72) = 1
                    i     stack = [2(75)]
                          answer = [1,1,0,2,1,1,0,0]

[73,74,75,71,69,72,76,73] 6(76) - 2(75) = 4
                    i     stack = [6(76)]
                          answer = [1,1,4,2,1,1,0,0]

[73,74,75,71,69,72,76,73] stack = [6(76),7(73)]
                       i  answer = [1,1,4,2,1,1,0,0]

Code:

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  const answer = temperatures.map(() => 0);
  const stack = [];
  for (let i in temperatures) {
    while (
      stack.length > 0 &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const poppedIdx = stack.pop();
      answer[poppedIdx] = i - poppedIdx;
    }
    stack.push(i);
  }
  return answer;
};

Reference

Original link

Monotonic stack intro