每日温度

发表于
本文字数： 1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，739.Daily Temperatures

先看题目描述

大意就是给定一个整型数组表示每天的温度，需要输出一个数组，第 i 项就表示对于第 i 天来说过几天后温度会比 T[i] 高，若第 i 天没有比 T[i] 高的温度，则输出的第 i 项为 0

算法和思路

这道题和之前做过的柱状图中的最大矩形十分相似，是同一类型的题，用单调栈就可以解决，不过那道题是单调递增栈，这个是递减栈，我们可以将天数一个个添加到栈中，当添加的天数对应温度大于栈顶天数对应温度时，则输出数组里栈顶天数对应的值便可以得到

算法流程

  • 定义一个 res 数组用来返回结果，定义一个栈 stack 用于辅助计算

  • 遍历 T 数组，当遍历到第 i 个元素时

  • 若栈为空，则将 i 直接入栈

  • 若栈不为空，比较栈顶元素 left 对应温度与 T[i]

    • 若 T[left] >= T[i]，将 i 直接入栈
    • 若 T[left] < T[i]，则将 left 出栈，res[left] = i - left

  • 重复上述过程直到 T[left] >= T[i]，将 i 入栈

  • 遍历完 T 数组以后返回 res 数组

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        Deque<Integer> stack = new ArrayDeque<>(len);
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && T[stack.peek()] < T[i]) {
                int left = stack.pop();
                res[left] = i - left;
            }
            stack.push(i);
        }
        return res;
    }
}