javascript算法集：数组中最大差值｜斐波那契数列
数组中最大差值
方法一
|
1
2
3
|
function getMaxProfit1(ary){
return Math.max.apply(null, ary) - Math.min.apply(null, ary);
}
|
测试：getMaxProfit1([1, 2, 3, 4]) // 3
斐波那契数列
这里我们只实现通项公式
斐波那契数列 方法一
|
1
2
3
4
5
6
7
|
function fib1(n){
if(n === 1 || n === 2){
return 1;
}
return fib1(n - 1) + fib1(n - 2);
}
|
PS：时间复杂度为O(2^n)，空间复杂度为O(n)
斐波那契数列 方法二
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
function fib2(n){
let tem = [1, 1];
if(n === 1 || n === 2){
return 1;
}
// 数组索引从0开始，数列索引从1开始
for(let i = 2; i < n; i++){
tem[i] = tem[i-1] + tem[i-2];
}
return tem[n-1];
}
|
PS：时间复杂度为O(n)，空间复杂度为O(n)
斐波那契数列 方法三
|
1
2
3
4
5
6
7
8
9
10
11
12
|
function fib2(n){
let prev = 1,
next = 1,
res;
for(let i = 2; i < n; i++){
res = prev + next;
prev = next;
next = res;
}
return res;
}
|
PS：时间复杂度为O(n)，空间复杂度为O(1)
测试：fib2(3) // 2
THE END
