739. 每日溫度 還是單調棧

739. 每日溫度

難度：中等

題目描述

解題思路

寫了幾道單調棧的題目之後就直到套路啦~直接套模闆就可以了

public int[] dailyTemperatures(int[] T) {
        if(T.length == 0)
				 return T;
			 int[] re = new int[T.length];
			 Stack<Integer> stack = new Stack<>();
			 stack.push(0);
			 for (int i = 1; i < T.length; i++) {
				while(!stack.isEmpty() && T[i] > T[stack.peek()]) {
					int last = stack.pop();
					re[last] = i-last;
				}
				stack.push(i);
			}
			 return re;
    }
           

看評論發現還有一種思路，就是從後往前周遊。最後一天肯定是0，如果後一天大于前一天，那麼前一天就是1；如果比前一天小，那麼利用已經得到的結果（第一個比前一天小的天數）優化搜尋次數。這種思想可以看作是暴力解法的優化，實際送出結果還不錯。

public int[] dailyTemperatures(int[] T) {
        if(T.length == 0)
				 return T;
			 int[] re = new int[T.length];
			 for (int i = T.length - 2; i  >= 0; i--) {
				if(T[i] < T[i+1]) {//如果目前溫度比前一天嚴格小
					re[i] = 1;
				}else {
					int j = i+1+re[i+1];
					while(T[j] <= T[i] && re[j] != 0) {
						j += re[j];   //每次都直接找第一個比目前元素大的
					}
					if(T[j] > T[i])
						re[i] = j - i;
				}
			}
			 return re;
    }
           

也有點動态規劃那味了