力扣739:每日温度 (Java多种方法)

简介: 给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。

算法知识:判别是否需要使用单调栈,如果需要找到左边或者右边第一个比当前位置的数大或者小,则可以考虑使用单调栈


一、题目描述



给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。


示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]

输出: [1,1,4,2,1,1,0,0]


示例 2:

输入: temperatures = [30,40,50,60]

输出: [1,1,1,0]


示例 3:

输入: temperatures = [30,60,90]

输出: [1,1,0]


提示:

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100


二、思路讲解及代码实现



1、暴力

     

直接暴力的解法是超时的,于是用一个highTem数组来保存之后出现的较高温度是多少,能够减少向后遍历的查找次数。


(因为30<=temperatures[i]<=100,所以,可以用一个长度为71的数组来保存每个温度第一次出现的索引,也能够提升查找的效率。这里就不展开了。)

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int []answer = new int[len];    //所求结果
        int []highTem = new int[len];   //highTem[i]表示第i天之后的更高温度是多少
        for(int i=len-2; i>=0; i--) {
            if(answer[i+1] == 0) {  //说明后面没有比temperatures[i+1]更高的温度
                if(temperatures[i] >= temperatures[i+1]){
                    answer[i] = 0;
                } else {
                    answer[i] = 1;
                    highTem[i] = temperatures[i+1];
                }
            } else {
                if(temperatures[i] < temperatures[i+1]) {
                    answer[i] = 1;
                    highTem[i] = temperatures[i+1];
                } else {
                    //去找高温
                    for(int j=i; j<len; j++) {
                        if(highTem[j] > temperatures[i]) {
                            answer[i] = j-i + answer[j];
                            highTem[i] = highTem[j];
                            break;
                        }
                    }
                }
            }
        }
        return answer;
    }
}


2、单调栈

     

判别是否需要使用单调栈,如果需要找到左边或者右边第一个比当前位置的数大或者小,则可以考虑使用单调栈


维护一个栈,里面存放温度对应的索引(因为题目中求的是天数,不是温度)。如果栈为空或者栈顶温度大于当前温度,直接入栈;如果栈顶温度小于当前温度,说明当前温度即为栈顶温度要找的温度,出栈后继续比较栈顶温度。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int []answer = new int[len];    //所求结果
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<len; i++) { 
            //一直要把小于当前温度的都出栈,因为当前温度就是他们要找的温度
            while(!stack.isEmpty() && temperatures[stack.peek()]<temperatures[i]) {
                int index = stack.pop();
                answer[index] = i - index;
            }
            stack.add(i);
        }
        return answer;
    }
}



相关文章
|
9天前
|
Java API
Java 对象释放与 finalize 方法
关于 Java 对象释放的疑惑解答,以及 finalize 方法的相关知识。
34 17
|
3天前
|
Java 测试技术 Maven
Java一分钟之-PowerMock:静态方法与私有方法测试
通过本文的详细介绍,您可以使用PowerMock轻松地测试Java代码中的静态方法和私有方法。PowerMock通过扩展Mockito,提供了强大的功能,帮助开发者在复杂的测试场景中保持高效和准确的单元测试。希望本文对您的Java单元测试有所帮助。
8 2
|
11天前
|
Java 开发者
在Java多线程编程中,创建线程的方法有两种:继承Thread类和实现Runnable接口
【10月更文挑战第20天】在Java多线程编程中,创建线程的方法有两种:继承Thread类和实现Runnable接口。本文揭示了这两种方式的微妙差异和潜在陷阱,帮助你更好地理解和选择适合项目需求的线程创建方式。
12 3
|
11天前
|
Java 开发者
在Java多线程编程中,选择合适的线程创建方法至关重要
【10月更文挑战第20天】在Java多线程编程中,选择合适的线程创建方法至关重要。本文通过案例分析,探讨了继承Thread类和实现Runnable接口两种方法的优缺点及适用场景,帮助开发者做出明智的选择。
10 2
|
11天前
|
安全 Java
Java多线程通信新解:本文通过生产者-消费者模型案例,深入解析wait()、notify()、notifyAll()方法的实用技巧
【10月更文挑战第20天】Java多线程通信新解:本文通过生产者-消费者模型案例,深入解析wait()、notify()、notifyAll()方法的实用技巧,包括避免在循环外调用wait()、优先使用notifyAll()、确保线程安全及处理InterruptedException等,帮助读者更好地掌握这些方法的应用。
11 1
|
11天前
|
Java 开发者
Java多线程初学者指南:介绍通过继承Thread类与实现Runnable接口两种方式创建线程的方法及其优缺点
【10月更文挑战第20天】Java多线程初学者指南:介绍通过继承Thread类与实现Runnable接口两种方式创建线程的方法及其优缺点,重点解析为何实现Runnable接口更具灵活性、资源共享及易于管理的优势。
22 1
|
11天前
|
Java
在Java多线程编程中,`wait()`和`notify()`方法的相遇如同一场奇妙的邂逅
在Java多线程编程中,`wait()`和`notify()`方法的相遇如同一场奇妙的邂逅。它们用于线程间通信,使线程能够协作完成任务。通过这些方法,生产者和消费者线程可以高效地管理共享资源,确保程序的有序运行。正确使用这些方法需要遵循同步规则,避免虚假唤醒等问题。示例代码展示了如何在生产者-消费者模型中使用`wait()`和`notify()`。
17 1
|
11天前
|
安全 Java 开发者
Java多线程中的`wait()`、`notify()`和`notifyAll()`方法,探讨了它们在实现线程间通信和同步中的关键作用
本文深入解析了Java多线程中的`wait()`、`notify()`和`notifyAll()`方法,探讨了它们在实现线程间通信和同步中的关键作用。通过示例代码展示了如何正确使用这些方法,并分享了最佳实践,帮助开发者避免常见陷阱,提高多线程程序的稳定性和效率。
22 1
|
11天前
|
Java
在Java多线程编程中,`wait()` 和 `notify()/notifyAll()` 方法是线程间通信的核心机制。
在Java多线程编程中,`wait()` 和 `notify()/notifyAll()` 方法是线程间通信的核心机制。它们通过基于锁的方式,使线程在条件不满足时进入休眠状态,并在条件成立时被唤醒,从而有效解决数据一致性和同步问题。本文通过对比其他通信机制,展示了 `wait()` 和 `notify()` 的优势,并通过生产者-消费者模型的示例代码,详细说明了其使用方法和重要性。
18 1
|
5天前
|
Java Spring
JAVA获取重定向地址URL的两种方法
【10月更文挑战第17天】本文介绍了两种在Java中获取HTTP响应头中的Location字段的方法:一种是使用HttpURLConnection,另一种是使用Spring的RestTemplate。通过设置连接超时和禁用自动重定向,确保请求按预期执行。此外,还提供了一个自定义的`NoRedirectSimpleClientHttpRequestFactory`类,用于禁用RestTemplate的自动重定向功能。