题目描述
力扣城计划在两地设立「力扣嘉年华」的分会场,气象小组正在分析两地区的气温变化趋势,对于第 i ~ (i+1)
天的气温变化趋势,将根据以下规则判断:
- 若第
i+1
天的气温 高于 第i
天,为 上升 趋势 - 若第
i+1
天的气温 等于 第i
天,为 平稳 趋势 - 若第
i+1
天的气温 低于 第i
天,为 下降 趋势
已知 temperatureA[i]
和 temperatureB[i]
分别表示第 i
天两地区的气温。
组委会希望找到一段天数尽可能多,且两地气温变化趋势相同的时间举办嘉年华活动。请分析并返回两地气温变化趋势 相同的最大连续天数。
即最大的
n
,使得第i~i+n
天之间,两地气温变化趋势相同
样例
输入:
temperatureA = [21,18,18,18,31]
temperatureB = [34,32,16,16,17]
输出:2
解释:如下表所示,第 2~4 天两地气温变化趋势相同,且持续时间最长,因此返回 4-2=2
输入:
temperatureA = [5,10,16,-6,15,11,3]
temperatureB = [16,22,23,23,25,3,-16]
输出:3
限制
2 <= temperatureA.length == temperatureB.length <= 1000
-20 <= temperatureA[i], temperatureB[i] <= 40
算法
(线性扫描) $O(n)$
- 将两个数组做差分求出趋势数组,然后比对两个数字找到最大连续的相同区间。
时间复杂度
- 遍历数组若干次,故时间复杂度为 $O(n)$。
空间复杂度
- 原地做差分比较,仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int temperatureTrend(vector<int>& temperatureA, vector<int>& temperatureB) {
const int n = temperatureA.size();
for (int i = 0; i < n - 1; i++)
if (temperatureA[i] < temperatureA[i + 1])
temperatureA[i] = 1;
else if (temperatureA[i] > temperatureA[i + 1])
temperatureA[i] = -1;
else
temperatureA[i] = 0;
for (int i = 0; i < n - 1; i++)
if (temperatureB[i] < temperatureB[i + 1])
temperatureB[i] = 1;
else if (temperatureB[i] > temperatureB[i + 1])
temperatureB[i] = -1;
else
temperatureB[i] = 0;
int ans = 0;
for (int i = 0, last = 0; i < n; i++)
if (i == n - 1 || temperatureA[i] != temperatureB[i]) {
ans = max(ans, i - last);
last = i + 1;
}
return ans;
}
};