Daily Temperatures


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;
}
}

My solution offers the same complexity, but relying on
O(N)
storage (onlyT
, 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 temperaturen = N1, N2, ..., 0
, we either havetemperature[n] < temperature[n + 1]
in which case
T[n] = 1
and we can proceed to the next value. Otherwise, we havetemperature[n] >= temperature[n + 1]
in which case we find the next warmer day as follows:
If
T[n + 1] = 0
, we know thatT[n] = 0
and can proceed to the next case. This is becausetemperature[n]
is already warmer thantemperature[n + 1]
, andT[n + 1] = 0
tells us that there are no future days warmer thantemperature[n + 1]
.If, on the other hand,
T[n + 1] > 0
, we skip toT[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 ofN M
isO(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; }

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.length1; 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;

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;