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?


  • 0
    F

    Don't see why we do it backwards. Unnecessary IMHO.

    int[] result = new int[temperatures.length];
    Stack<Integer> stack = new Stack<>(); // Make it a stack of indices.
    for (int i = 0; i < temperatures.length; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int index = stack.pop();
            result[index] = i - index;
        }
        stack.push(i);
    }
    return result;
    

  • 0
    A

    The output of "Next Array" method is [0,0,0,0,0,0,0], is there anyone get the same result as mine?


Log in to reply
 

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