当前位置: 首页 > news >正文

昆明高端网站建设泉州百度关键词优化

昆明高端网站建设,泉州百度关键词优化,360网站优化,想设计一个自己的logo给定一个整数数组 temperatures,表示每天的温度,要求返回一个数组 answer,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。 问题分析 我们需要计算…

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


问题分析

我们需要计算每一天之后需要等多少天才能遇到更高的温度。如果无法找到更高的温度,就返回 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]


解题思路:使用单调栈

在这个问题中,我们要计算每个温度之后,需要多少天才会遇到一个更高的温度。一个直接的暴力解法是,对每一天,从它之后的所有天中查找第一个更高的温度,这样会导致 O(n^2) 的时间复杂度。显然,暴力解法并不高效,特别是对于较大的输入。

为了提高效率,我们可以使用一个单调栈来将时间复杂度降低到 O(n)。下面是具体的思路:

关键步骤:

  1. 从后向前遍历:我们从最后一天开始遍历,每次都试图通过栈来维护一个"待解决"的温度序列。这样可以更容易地通过栈找到每个温度的下一个更高温度。

  2. 维护递减栈:栈中存储的是当前遍历过的温度的索引,并且栈中的温度是递减的。这意味着栈顶的元素对应的温度是当前栈中最小的(即当前最可能成为下一个更高温度的温度)。

  3. 遇到更高温度时计算天数:如果栈顶元素的温度比当前温度低,我们就可以计算该元素的下一个更高温度的天数。

  4. 栈顶小于等于当前温度时,出栈:如果栈顶的温度小于当前温度,那么说明当前温度是下一个更高温度的候选,因此栈顶元素出栈,继续判断下一个栈顶元素。

  5. 栈顶大于当前温度时,计算等待天数:栈顶元素的温度大于当前温度时,说明找到了下一个更高的温度,计算距离当前天数的差。

  6. 压入当前索引:最后,将当前温度的索引压入栈中,准备处理下一个温度。


代码实现:

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] ans = new int[n];  // 用来存储每一天之后需要等待的天数Deque<Integer> st = new ArrayDeque<>();  // 单调栈,存储索引// 从后往前遍历for (int i = n - 1; i >= 0; i--) {int t = temperatures[i];  // 当前温度// 维护单调递减栈:移除栈顶比当前温度低的元素while (!st.isEmpty() && t >= temperatures[st.peek()]) {st.pop();  // 弹出栈顶温度比当前低的元素}// 栈不为空,说明有比当前温度更高的温度if (!st.isEmpty()) {ans[i] = st.peek() - i;  // 计算等待天数}// 将当前天的索引压入栈中st.push(i);}return ans;  // 返回结果数组}
}

代码详解:

  1. 栈的作用:栈存储的是温度的索引,而不是温度本身,这样可以方便计算等待天数。

  2. 逆序遍历:从最后一天开始,逐步处理每一天的温度。这是因为我们需要查找每一天之后第一个更高的温度,而如果从前向后遍历就需要不断地返回去查找,效率较低。

  3. 栈的更新:每当我们遇到比栈顶元素小的温度时,栈顶元素的下一次更高温度就是当前温度,计算并记录等待的天数。如果栈顶元素比当前温度大,说明栈顶的温度就是下一个更高温度,记录下来。


时间复杂度分析:

  • 时间复杂度O(n)。每个温度索引最多入栈一次,出栈一次,因此栈的操作总共执行 n 次。

  • 空间复杂度O(n)。我们使用了一个栈来存储索引,最多需要存储 n 个元素。


总结:

通过使用单调栈的技巧,我们能够将时间复杂度从暴力解法的 O(n^2) 优化到 O(n),极大地提升了算法效率。这个方法利用栈来存储待解决的温度索引,并通过栈顶元素的温度与当前温度的比较,快速找到每一天需要等待的天数。


希望这篇文章能够帮助你更好地理解和掌握单调栈的应用技巧!如果你有任何疑问或更好的优化思路,欢迎在评论区留言讨论!

http://www.khdw.cn/news/20615.html

相关文章:

  • 免费网站建设特色中国搜索引擎市场份额
  • 政府网站建设网页设计规范网络推广员是什么
  • 昭通建网站做网站的费用
  • 贵州专业网站建设公司查询域名注册信息
  • 网站建设的公司推荐淘宝代运营公司排名
  • 河北城乡建设厅网站百度知道在线问答
  • 高端网站设计报价表哪里有培训网
  • 深圳怎么做网站微信营销推广方案
  • 邳州网站建设广东最新疫情
  • 自家房子做民宿的网站市场营销互联网营销
  • 济源网站制作最好的免费推广平台
  • 曲靖手机网站建设昆明抖音推广
  • 佘山网站建设百度提交网址入口
  • 网站制作怎么创业河南网站排名
  • 做网站开视频网站游戏推广代理加盟
  • 个人网站建设培训竞价排名规则
  • 房山营销型网站建设哈尔滨最新消息
  • 国外做游戏的视频网站有哪些视频seo优化教程
  • 宜昌平台网站建设近10天的时事新闻
  • 做网站那里做可靠晨阳seo顾问
  • 化妆品网页设计论文seo优化seo外包
  • 注册公司费用是多少网站seo内容优化
  • 朔州推广型网站建设网络营销措施有哪些
  • 营销培训课程有哪些旺道seo系统
  • 怎么做免费的网站链接2022年新闻大事
  • wordpress 怎样写函数长沙企业seo服务
  • 怎样做网站呢长春网站制作计划
  • 网站有后台更新不了培训网站推广
  • 香港网站速度慢广州百度关键词搜索
  • 做网站生意不赚钱怎样推广品牌