Daily Temperatures


  • 0

    Click here to see the full article post


  • 0
    H

    How about this in C#?

    public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
    int[] temp = new int[temperatures.Length];
    for(int i = 0; i < temperatures.Length; i++){
    int tmp = 0;
    bool isChecked = false;
    for(int j = i + 1; j < temperatures.Length && !isChecked; j++){
    tmp++;
    if(temperatures[j] > temperatures[i]){
    temp[i] = tmp;
    isChecked = true;
    }
    }
    }
    return temp;
    }
    }


  • 0
    T

    The idea of my solution was the same as in the stack approach but I implemented it through a dictionary/HashMap with items of the form {temp : date}. How much could it affect the complexity of the algorithm?


  • 0
    P

    My solution offers the same complexity, but relying on O(N) storage (only T, the list containing the result); it is based on Dynamic Programming.

    The base case is the last temperature, for which T[N] = 0. For every subsequent temperature n = N-1, N-2, ..., 0, we either have

    temperature[n] < temperature[n + 1]
    

    in which case T[n] = 1 and we can proceed to the next value. Otherwise, we have

    temperature[n] >= temperature[n + 1]
    

    in which case we find the next warmer day as follows:

    If T[n + 1] = 0, we know that T[n] = 0 and can proceed to the next case. This is because temperature[n] is already warmer than temperature[n + 1], and T[n + 1] = 0 tells us that there are no future days warmer than temperature[n + 1].

    If, on the other hand, T[n + 1] > 0, we skip to T[n + 1 + T[n + 1]] and repeat the rationale.

    The inner loop will traverse at most as many times as there are temperatures, so it is bounded above by M (the number of possible temperatures), therefore the complexity of N M is O(N).

      vector<int> dailyTemperatures(vector<int>& temperatures) {
        const auto N = temperatures.size();
    
        if (N == 1) return {0};
    
        vector<int> T(N, 0);
    
        for (auto k = N - 2; k < N; --k) {
          if (temperatures[k] < temperatures[k + 1]) {
            T[k] = 1;
            continue;
          }
    
          if (T[k + 1] == 0) continue;
    
          for (auto j = k + 1 + T[k + 1]; j < N; j += T[j]) {
            if (temperatures[k] < temperatures[j]) {
              T[k] = j - k;
              break;
            }
            if (T[j] == 0) break;
          }
        }
    
        return T;
      }
    

  • 0
    P

    an O(n*2) algorithm passes the tests (ie, brute force check), so maybe that should be documented or ruled out in the testing.


  • 0
    P

    this is super brute force and passes but no ideal obviously....

       public int[] dailyTemperatures(int[] temperatures) {
            int[] ret = new int[temperatures.length];
            
            for (int i = 0; i < temperatures.length-1; i++){
                int x = temperatures[i];
                ret[i] = 0;
                for (int j = i+1; j < temperatures.length; j++){
                    int y = temperatures[j];
                    if (y - x > 0){
                        ret[i] = j - i;
                        break;
                    }
                }
            }
            return ret;
    

  • 0
    D

    Should the size of the stack represent the longest run of decreasing temperature?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.