1
\$\begingroup\$

https://leetcode.com/problems/daily-temperatures/

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].

Please review for performance.

using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/daily-temperatures/
    /// </summary>
    [TestClass]
    public class DailyTemperaturesTest
    {
        [TestMethod]
        public void ExmapleTest()
        {
            int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
            int[] days = {1, 1, 4, 2, 1, 1, 0, 0};
            CollectionAssert.AreEqual(days, DailyTemperaturesClass.DailyTemperatures(temperatures));
        }

        [TestMethod]
        public void SmallExampleTest()
        {
            int[] temperatures = {73, 72, 73, 74};
            int[] days = {3, 1, 1, 0};
            CollectionAssert.AreEqual(days, DailyTemperaturesClass.DailyTemperatures(temperatures));
        }
    }

    public class DailyTemperaturesClass
    {
        public static int[] DailyTemperatures(int[] T)
        {
            int[] days = new int[T.Length];
            // we are using a stack to remeber all the temps we saw until now,
            // the next time we see one which is higher we pop all the temps which are lower
            Stack<int> stack = new Stack<int>();
            for (int i = T.Length - 1; i >= 0; i--)
            {
                //if the current temp is greater or equals to the top of the stack
                // pop all until found one which is higher temp then T[i]
                while (stack.Count > 0 && T[i] >= T[stack.Peek()])
                {
                    stack.Pop();
                }

                if (stack.Count == 0)
                {
                    days[i] = 0;
                }
                else
                {
                    days[i] = stack.Peek() - i; // number of days between higher temp to i
                }
                stack.Push(i);// we push current temp to the Top of the stack.
            }

            return days;
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.