Дневные температуры

Дан список (массив) дневных температурT, вернуть такой массив, в котором в каждому дню будет соответствовать число, сколько дней ждать повышения температуры. Если повышения не предвидится для какого-то дня, то ему поставить 0 .

Например, массив температур: T = [73, 74, 75, 71, 69, 72, 76, 73], результат будет [1, 1, 4, 2, 1, 1, 0, 0].

Примечание: Длинна массива temperatures находится в интервале [1, 30000]. Каждая температура - это целое число в интервале [30, 100].

Идея решения: здесь удобно начать с конца массива. Для финального элемента повышения не будет, поэтому сразу запишем последний элемент в массиве результата 0.

Смотрим предпоследний элемент. Два случая:

• Если он больше последнего, то ставим опять 0 (повышения не произошло до конца массива). 
• Если он меньше последнего, то повышение температуры происходит на следующий день и мы ставим 1.

Смотрим третий с конца элемент. Тут четыре ситуации. Пусть X, Y, Z - это три последних элемента массива. Индексы у них, соответственно ind1, ind2, ind3 (например, 5, 6, 7).

1. X > Y > Z - температура постоянно падает, в ответе везде будет 0.
2. X < Y > Z - рассмотрим соотношение X и Z
1. X > Z или Z < X <Y, то есть температура после X выросла, а потом опять упала меньше X, ответ будет 1, 0, 0
2. X < Z или X < Z < Y, то есть  температура после X выросла, а потом опять упала меньше Y, но больше X, ответ будет 1, 0, 0
3. X < Y < Z - ответ будет 1, 1, 0
4. X > Y < Z - ответ будет 
1. X > Z или X > Z > Y, то есть для X больше не было повышения температуры, но она была для  Y, ответ будет 0, 1, 0
2. X < Z или Z >X > Y тут после X было падение температуры на следующий день, но через два дня (относительно X) было повышение, то есть ответ 2, 1, 0

Обобщаем: если несколько дней подряд идёт падение, а потом температура, которая перебивает весь этот интервал падения, то для каждого из таких дней мы ставим index_день_повышения-index_день_падения.

Для запоминания такой динамики роста-снижения подходит структура данных стек (stack).
В стек мы закладываем индексы, когда температура растёт. В нашем случае 4.2:

• при рассмотрении Z не с чем сравнивать, поэтому индекс 7 попадает в стек по умолчанию: {7};
• при рассмотрении Y, Y<Z, температура растёт, это может растущая температура для какого-то предыдущая температура, поэтому заносим её в стек: {7, 6}.
• если X с индексом 5 больше Y, но меньше Z, то из стека удаляем 6 (падает относительно индекса 5) и добавляем 5, поскольку X может быть для кого-то растущей темепратурой: стек будет {7, 5}. Обратите внимание, что 7-5=2, то есть для X через 2 дня наступит потепление, что и было описано в случае 4.2.
• если же X<Y (случай 3), то имеем три подряд растущих темепартуры, стек равен {7, 6, 5}, разница между смежными элементами = 1, поэтому результат = 1, 1, 0.

Решение: 

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length]; // сюда записываем результат
        Stack<Integer> stack = new Stack(); // наш стек
        for (int i = T.length - 1; i >= 0; --i) { // идём с конца массива
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) stack.pop();
// в цикле while выбрасываем из стека все элементы, которые меньше текущей температуры
// если выбросили из стека всё, то повышения не предвидится, записываем 0
// если что-то осталось, то самый верхний элемент стека - это ближайший день,
// когда будет повышение температуры, считаем разницу и записываем в ответ
            ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
// текущий элемент может быть растущей температурой для элементов, которые нам предстоит рассмотреть,
// поэтому помещаем его в стек.
// Если в стеке остались индексы, то они показывают растущую последовательность температур.
            stack.push(i);
        }
        return ans;
    }
}