求LeetCode爬楼梯问题的O(logn)复杂度高效解法

你的O(n)迭代解法逻辑正确，通过滚动变量避免了额外空间，已经是线性时间里的最优实现。要达到O(logn)的时间复杂度，我们可以利用矩阵快速幂或斐波那契通项公式来实现，以下是具体方案：

方法一：矩阵快速幂 #

爬楼梯的递推关系 f(n) = f(n-1) + f(n-2) 可以转化为矩阵幂运算：
$$
\begin{bmatrix} f(n) \ f(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} f(1) \ f(0) \end{bmatrix}
$$
其中 f(1)=1，f(0)=1（对应n=1时的结果）。通过快速幂算法计算矩阵的n-1次幂，时间复杂度为O(logn)。

C# 实现代码 #

public class Solution {
    public int ClimbStairs(int n) {
        if (n <= 2) return n;
        int[,] matrix = {{1, 1}, {1, 0}};
        int[,] result = MatrixPower(matrix, n - 1);
        return result[0, 0];
    }

    private int[,] MatrixPower(int[,] a, int power) {
        // 初始化单位矩阵
        int[,] result = {{1, 0}, {0, 1}};
        while (power > 0) {
            if (power % 2 == 1) {
                result = MultiplyMatrices(result, a);
            }
            a = MultiplyMatrices(a, a);
            power /= 2;
        }
        return result;
    }

    private int[,] MultiplyMatrices(int[,] a, int[,] b) {
        int[,] res = new int[2, 2];
        res[0, 0] = a[0, 0] * b[0, 0] + a[0, 1] * b[1, 0];
        res[0, 1] = a[0, 0] * b[0, 1] + a[0, 1] * b[1, 1];
        res[1, 0] = a[1, 0] * b[0, 0] + a[1, 1] * b[1, 0];
        res[1, 1] = a[1, 0] * b[0, 1] + a[1, 1] * b[1, 1];
        return res;
    }
}

方法二：斐波那契通项公式（比内公式） #

利用斐波那契数列的通项公式直接计算，公式为：
$$
f(n) = \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right)
$$
注意爬楼梯的第n项对应斐波那契数列的第n+1项，因此代入时需要调整参数。由于浮点数运算存在精度误差，最后需要取整处理。

C# 实现代码 #

public class Solution {
    public int ClimbStairs(int n) {
        double sqrt5 = Math.Sqrt(5);
        double fibn = Math.Pow((1 + sqrt5) / 2, n + 1) - Math.Pow((1 - sqrt5) / 2, n + 1);
        return (int)(fibn / sqrt5);
    }
}

你的原O(n)解法代码 #

public class Solution {
    public int ClimbStairs(int n) {
        //quick base case
        if (n <= 3 && n > 0) return n;

        //working total variables
        int total = 6, now = 2, next = 3;

        //for loop to calculate total
        for (int index = 3; index < n; index++) {
            total = now + next;
            now = next;
            next = total;
        }
        return total;
    }
}

内容的提问来源于stack exchange，提问作者Nash Carroll