Leetcode. 739 每日温度

2024-02-25 05:44
文章标签 leetcode 每日 温度 739

本文主要是介绍Leetcode. 739 每日温度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目信息

LeetoCode地址: . - 力扣(LeetCode)

题目理解

题意很好理解,找到比每日温度更高的温度的已过天数的偏移量。如果找不到,则设为0。

最直观的想法是,从每一天开始向后一天一天找,直到找到更高温度的那一天。但是这种做法时间复杂度过高,有太多重复的操作,因此需要找更优的算法。

单调栈写法

容易发现,当遍历到第i天,温度为25度的前提下,如果第i+1天的温度比25度高,则第i天的结果很好计算,即是1. 如果第i+1天的温度没超过2度,则暂时得不到结果,那不如先将第i+1天的温度暂存起来,继续看第i+2天,如果温度继续走低,则继续看后一天。直到某一天温度比前一天高,假设第j天,则我们可以在暂存区里拿出来这一天,将结果求出。类似的,我们可以将暂存区里更之前的温度也拿出来和第j天对比,求出结果,直到暂存区里的温度都比第j天高,此时再将第j天的温度放入暂存区,重复该过程。

这个暂存区的存取总是后放入的先拿出来计算,很显然是栈的操作,所以这种做法就是单调栈做法。

在temperatures数组的长度为l的情况下,

时间复杂度: O(l), 因为我们对每一个温度只会有三种操作,放入栈,拿出栈,或者直接计算偏移量。

额外空间复杂度:O(l),我们需要一个大小为l的栈存放持续走低的温度数据,直到遇到更大的。

class Solution {public int[] dailyTemperatures(int[] temperatures) {int l = temperatures.length;int[] stack = new int[l];int stackTopIndex = -1;int[] result = new int[l];int i = 0;while (i < l) {if (stackTopIndex == -1) {stack[++stackTopIndex] = i++;} else {if (temperatures[i] <= temperatures[stack[stackTopIndex]]) {stack[++stackTopIndex] = i++;} else {result[stack[stackTopIndex]] = i - stack[stackTopIndex];stackTopIndex--;}}}return result;}
}

动态规划写法

如何能利用之前算过的数据来推导还未计算过的温度的偏移量呢?让我们分析一下。

很显然,最后一天的温度的更高温度偏移量为0,因为后面没有数据了。

倒数第二天的温度如果比最后一天低,则偏移量为1;相反,如果相同或者更高,则可以根据后一天的偏移量, 这里最后一天的偏移量是0,所以倒数第二天的偏移量也是0;

...

倒数第n天,类似的,先看n+1天,如果温度更高了,则偏移量为1; 相反,则看n+1天的偏移量之后的温度,更高了,则偏移量(n) = 1 + 偏移量(n+1);如果温度还是不够高,则继续看其偏移量,直到满足条件,或者到达最后一天。

这种根据已有的结果计算其他数据的思想就是动态规划。

在temperatures数组的长度为l的情况下,

时间复杂度: O(l), 看似我们有循环操作,但是它们搜索的数据空间没有重复,因此时间复杂度是O(l).

额外空间复杂度:O(1), 除了存放结果的集合,不需要其他额外的空间。

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

这篇关于Leetcode. 739 每日温度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/744549

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl