739.每日温度

题目描述

题解

暴力解法

使用双循环将每天的温度作为起点往后查找比它大的第一个数, 找到后将两个下标的差值作为结果保存

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            int j = i + 1;

            while (j < T.length) {
                if (T[j] > T[i]) {
                    res[i] = j - i;
                    break;
                }
                j++;
            }

            if (j == T.length){
                res[i] = 0;
            }
        }

        return res;
    }
}

栈

利用栈结构, 在栈里存的是递减的数字.

每遍历到一个数字, 将其与栈顶元素进行比较, 如果比栈顶元素小, 就入栈, 如果比栈顶元素大, 弹出栈顶元素并将差值作为结果记录下来, 然后与新的栈顶元素循环比较, 知道比栈顶元素小或者栈为空, 然后将该元素入栈.

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < T.length; i++) {
            if (stack.isEmpty() || T[i] < T[stack.getLast()]) {
                stack.addLast(i);
            } else {
                while (!stack.isEmpty() && T[i] > T[stack.peekLast()]) {
                    int temp = stack.pollLast();
                    res[temp] = i - temp;
                }
                stack.addLast(i);
            }
            if (i == T.length - 1 && !stack.isEmpty()) {
                while (!stack.isEmpty()) {
                    res[stack.pollLast()] = 0;
                }
            }
        }

        return res;
    }
}