力扣 - 739. 每日温度

题目

739. 每日温度

思路1（暴力破解）

• 遍历每一个元素，从他的后一个元素开始寻找比他大的元素，如果遇到的是比他小于等于的，那就跳过，继续往后找
• 如果找到最后一个都还没找到比他大的，那么就直接赋值为0

代码

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];

        for (int i = 0; i < T.length - 1; i++) {
            int j = i + 1;
            while (j < T.length && T[i] >= T[j]) {
                j++;
            }
            if (j != T.length) {
                res[i] = j - i;
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：\(O(N^2)\)，其中 N 为数组的长度
• 空间复杂度：\(O(N)\)，其中 N 为数组的长度

思路2（单调栈）

• 由于是找到最近的比当前温度高的距离，所以可以使用单调递增栈
• 只有当前温度大于栈顶温度，那么才将栈元素出栈，直到小于栈元素才停止，否则的话，直接入栈
• 我们的单调栈中寸的是索引index，而不是元素的值，这样计算距离时直接用index相减即可得到结果

代码

class Solution {
    public int[] dailyTemperatures(int[] T) {
        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[T.length];

        for (int i = 0; i < T.length; i++) {
            // 只有大于栈顶元素才出栈
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int peek = stack.pop();
                res[peek] = i - peek;
            }
            // 每次都要将当前索引入栈
            stack.push(i);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)，其中 N 为数组长度
• 空间复杂度：\(O(N)\)，其中 N 为数组长度