(739) According to the list of temperatures every day, we need to wait several days before higher temperatures occur. If the temperature does not rise after that point, substitute 0 at that point. Example 1: input: temperatures =,74,75,71,69,72,76,73 [73] output:,1,4,2,1,1,0,0 [1]

The original problem is here.

Violence law

The first is the violence law, which is copied directly from a comment

int[] result = new int[temperatures.length]; for (int i = 0; i < temperatures.length; i++) { for (int j = i + 1; j < temperatures.length; j++) { if (temperatures[i] < temperatures[j]) { result[i] = j - i; break; }}} return result;Copy the code

This method is also easier to understand, starting with the first element in the array, and for each element, iterating back linearly, finding the first element that is larger than it, setting the value of the result array, break this loop.

The violent method of official problem solving

int len = temperatures.length; int[] res = new int[len]; int[] next = new int[101]; Arrays.fill(next,Integer.MAX_VALUE); for(int i=len-1; i>-1; --i){ int index = Integer.MAX_VALUE; for(int t=temperatures[i]+1; t<101; ++t) index = Math.min(index,next[t]); if(index<Integer.MAX_VALUE) res[i] = index-i; next[temperatures[i]] = i; } return res;Copy the code

This method is called “brute force” by the official solution, but it feels much better than the brute force method above, and the final result is similar to the performance of the monotone stack method. This method traverses from right to left, using a next array to record the leftmost coordinates of each temperature as of the point traversed… And the elements in the next array are initialized to integer. MAX_VALUE, so when we go to a temperature tempretures[I], we just need to go through the next array, starting with tempretures[I]+1. All of these temperatures are greater than tempretures[I]. Then, by traversing the next array, it is easy to obtain the current leftmost coordinate index of these temperatures greater than Tempretures [I], which is the solution to the problem. After next[temperatures[I]]= I, update the next array of the current temperature. If index= INTEger.max_value, it means that no temperature greater than the current temperature has been explored, that is, there is no temperature greater to the right of this temperature. The default value of an int array element in Java is 0. Why traverse from right to left? Because for each temperature, the qualified solution is only related to the number to its right, so let’s traverse from right to left, each time using the next array to record the current leftmost position of each temperature, and then the next array traversal, it is effective.

Monotonous stack method

int len = temperatures.length; int[] res = new int[len]; Deque<Integer> stack = new LinkedList<>(); for(int i=0; i<len; ++i){ while(! stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){ res[stack.peek()] = i-stack.peek(); stack.pop(); } stack.push(i); } return res;Copy the code

The idea is to iterate through a stack from left to right, and each time you add a new element to the stack, pop all the elements that are smaller than that element in the stack and update their solutions so that the elements in the stack are non-decrement (they can have the same element). This approach can understand it, assuming no the stack, we iterate through group from left to right, each traversal to a particular element, find it on the left side of all its smaller elements, with a record which visited array element solution has been obtained, next time no longer traverse, this is a double loop (violence is in fact the method). So now we have the stack, and we do the same thing, every time we go to an element, we set all the elements that are smaller than it and pop, so we don’t have to do anything with it next time, and we can make sure that each element gets popped by the first element on the right that is larger than it.

My own way

int len = temperatures.length; int[] res = new int[len]; for(int i=len-2; i>-1; --i){ if(temperatures[i]<temperatures[i+1]) res[i] = 1; else if(temperatures[i]==temperatures[i+1]) if(res[i+1]==0) res[i] = 0; else res[i] = res[i+1] + 1; else{ int count = res[i+1]+1; while(count+i<len){ if(temperatures[i+count]>temperatures[i]){ res[i] = count; break; } else if(temperatures[i+count]==temperatures[i]){ if(res[i+count]==0) res[i] = 0; else res[i] = count + res[i+count]; break; } else{ if(res[i+count]==0){ res[i] =0; break; } count += res[i+count]; } } } } return res;Copy the code

This method was written by myself at that time, I also saw similar in the comments of the solution of the problem, the code to write is quite long, mainly because the boundary conditions are a little too much, but the efficiency is good, from the submission situation, the time is about 1/3 of the monotonous stack, or ok! First of all, since the corresponding solution of each element is related to the solution to its right, so we traverse from right to left (refer to violence method), but can we not have linear ratio of each element? In fact, that will be more than a few times. (I +1) (I +1) (I +1) (I +1) (I +1) (I +1) (I +1) (I +1) (I +1) If temperatures [I] = temperatures [I + 1], the res res is [I] [I + 1) + 1, and is easy to understand, but note that if the res is 0, [I + 1] that there is no more temperatures [I + 1) larger number, both of it are equal, (1) Temperatures [I] are higher than 1 (I +1). (2) Temperatures [I +1] Because temperatures[I +1+res[I +1]] are the first number on the right that is larger than res[I +1], the temperatures between [I +1] and res[I +1] are less than or equal to [I +1]. Instead of having to compare temperatures to [I +1+res[I +1]], it’s the same thing to do every time we jump, trying to avoid overshooting the bounds. However, this code is rather long, I see in the solution to write more succinctly as follows:

int[] res = new int[len]; for(int i=len-2; i>-1; --i){ for(int j=i+1; j<len; j+=res[j]){ if(temperatures[j]>temperatures[i]){ res[i] = j-i; break; } else{ if(res[j]==0){ res[i]=0; break; } } } } return res;Copy the code

Actually and I am a meaning, but the family is much simpler ‘(>﹏<)’ first write, in fact, I’m segmented and the first indent, but didn’t see the effect in the preview area, don’t know to send can have indent effect