LeetCode739——每日温度

偏执的太偏执、 2022-01-23 06:13 274阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[https://leetcode-cn.com/problems/daily-temperatures/][https_leetcode-cn.com_problems_daily-temperatures]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：栈

### 思路一：暴力破解法 ###

时间复杂度在最差情况下是O(n ^ 2)，其中n为列表长度。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    
        public int[] dailyTemperatures(int[] T) {
            int n = T.length;
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (T[j] > T[i]) {
                        result[i] = j - i;
                        break;
                    }
                }
            }
            return result;
        }
    
    }

LeetCode解题报告：

![2019060219542515.png][]

### 思路二：对暴力破解法的优化 ###

从后往前遍历列表。最末端的位置一定是0，指针i从n - 2位置从后往前遍历数组T。

当T\[i\] == T\[i + 1\]和T\[i\] < T\[i + 1\]时均容易分析，但当T\[i\] > T\[i + 1\]时，我们需要从索引i + 1 + result\[i + 1\]开始往后遍历链表寻找那个大于T\[i\]的值。

时间复杂度在最差情况下是O(n ^ 2)，其中n为列表长度。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    
        public int[] dailyTemperatures(int[] T) {
            int n = T.length;
            int[] result = new int[n];
            result[n - 1] = 0;
            for (int i = n - 2; i >= 0; i--) {
                if (T[i] == T[i + 1]) {
                    if (result[i + 1] == 0) {
                        result[i] = 0;
                    } else {
                        result[i] = result[i + 1] + 1;
                    }
                } else if (T[i] < T[i + 1]) {
                    result[i] = 1;
                } else {
                    for (int j = i + 1 + result[i + 1]; j < n; j++) {
                        if (T[i] < T[j]) {
                            result[i] = j - i;
                            break;
                        }
                    }
                }
            }
            return result;
        }
    
    }

LeetCode解题报告：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1][]

### 思路三：利用栈 ###

栈中存放的是列表中的索引值，假设结果存储在result数组中。

指针i从索引为0的位置开始遍历列表T：

（1）设一个while循环，如果栈不为空且栈顶索引对应的列表T中的值小于当前T\[i\]，我们可以设置result\[栈顶值\] = 当前索引i - 栈顶值。

（2）在经过上述while循环后，每一个i都需要入栈。

时间复杂度和空间复杂度均是O(n)，其中n为列表的长度。

JAVA代码：

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

LeetCode解题报告：

![20190602200209338.png][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_daily-temperatures]: https://leetcode-cn.com/problems/daily-temperatures/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220123/1d3b1b8e309541c7876beb2686b1c76e.png
[2019060219542515.png]: /images/20220123/dfc84230d60c45ffb8be021bc9a355f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1]: /images/20220123/0d4f0c1e56d9409ebc2f1ac9136c152a.png
[20190602200209338.png]: /images/20220123/325be34d8a3949a29baedcd2153d162f.png