I firstly solved this problem bruteforcely, the solution is easy, but the time complexity is O(n2):
public int[] dailyTemperatures(int[] temperatures) { if(temperatures==null || temperatures.length==0) return null; int n = temperatures.length; int[] res = new int[n]; for(int i=0;i<temperatures.length;i++){ for(int j=i+1;j<temperatures.length;j++){ if(temperatures[j]>temperatures[i]){ res[i]=j-i; break; } } } return res; }
Then I studied monotonic stack a little bit, and write a new solution, the time complexity is O(2n)==O(n).
public int[] dailyTemperatures(int[] temperatures) { int[] res = new int[temperatures.length]; Stack<Integer> stk = new Stack<>(); for (int i = 0; i < temperatures.length; i++) { while (!stk.isEmpty() && temperatures[i] > temperatures[stk.peek()]) { res[stk.peek()] = i - stk.pop(); } stk.push(i); } return res; }