【LeetCode】找到最高海拔 Java 题解
题目描述
有一个自行车手打算进行一场公路骑行,这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。
给你一个长度为 n 的整数数组 gain ,其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差(0 <= i < n)。请你返回 最高点的海拔 。
复制代码
思路分析
今天的算法题目数组类型题目,题目要求计算出最高点的海拔。分析题目,关键描述是长度为 n 的整数数组 gain ,其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度,其中海拔为 0 的点初始值是 0。我们可以按照题意进行模拟,计算每一个点的海拔,然后动态更新最大值。具体实现代码如下,供参考。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(n),空间复杂度是 O(1)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/47bde64f31e98eb456ca2d409】。文章转载请联系作者。
评论