leetcode-739-Daily-Temperatures

发表于   |  

描述

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

分析

题目大意是给定一个数组，表示每天的温度，求每天经过多少天会升温。这里可以用后进先出的栈来维护还没有出现升温日的索引，遍历时的那一天温度高于栈顶时，表明找到了升温的那天，进行出栈操作，并记录结果，也就是说维护的栈会保持一个从栈顶到栈尾递增的顺序。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            while(!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int index = stack.pop();
                result[index] = i - index;
            }
            stack.push(i);
        }
        return result;
    }
}

相关问题

(E) Next Greater Element I

题目来源