[Leetcode][396. 旋转函数] 3种方法：暴力法，动态规划，前缀和 + 滑动窗口

By Long Luo

Leetcode 396. 旋转函数 题解。

方法一： 暴力法

思路与算法

很容易想到的方法是遍历，使用 $2$ 个循环，很明显最多只能有 $len$ 次旋转，因为对称性，所以数组下标可能会 $>= len$，所以要取余 $(i+j) \mod len$。

每次旋转更新最大值，时间复杂度为 $O(N^2)$。

// BF time: O(n^2) space: O(1)
   public int maxRotateFunction(int[] nums) {
       int len = nums.length;
       if (len <= 1) {
           return 0;
       }

       int ans = Integer.MIN_VALUE;
       for (int i = 0; i < len; i++) {
           int sum = 0;
           for (int j = 0; j < len; j++) {
               sum += j * nums[(i + j) % len];
           }

           ans = Math.max(ans, sum);
       }

       return ans;
   }

复杂度分析：

• 时间复杂度：$O(N^2)$，其中 $N$ 是数组 $\textit{nums}$ 的长度。

• 空间复杂度：$O(1)$。

方法二： 动态规划

思路与算法：

方法一会超时，其实观察旋转数组的变化：

$F(0) = 0 \times nums[0] + 1 \times nums[1] + \ldots + (n-1) \times nums[n-1]$

$F(1) = 1 \times nums[0] + 2 \times nums[1] + \ldots + 0 \times nums[n-1] = F(0) + \sum_{i=0}^{n-1}nums[i] - n \times nums[n-1]$

我们很容易发现相邻旋转的递推关系：

$F(k+1) = F(k) + \sum_{i=0}^{n-1}nums[i]-n \times nums[n-k], 0 \le k \lt n$

从$F(0)$出发，迭代计算出不同的$F(k)$，并求出最大值。

很容易使用DP写出如下代码：

// DP time: O(n) space: O(n)
public int maxRotateFunction_dp(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return 0;
    }

    int[] dp = new int[len];
    int sum = 0;
    for (int i = 0; i < len; i++) {
        dp[0] += i * nums[i];
        sum += nums[i];
    }

    int ans = dp[0];
    for (int i = 1; i < len; i++) {
        dp[i] = dp[i - 1] + sum - len * nums[(len - i) % len];
        ans = Math.max(ans, dp[i]);
    }

    return ans;
}

观察上述代码，我们发现dp[]数组只是记录数值，实际上可以将空间复杂度优化到$O(1)$。

// DP Opt time: O(n) space: O(1)
public int maxRotateFunction_dp_opt(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return 0;
    }

    int ans = 0;
    int sum = 0;
    for (int i = 0; i < len; i++) {
        ans += i * nums[i];
        sum += nums[i];
    }

    int pre = ans;
    for (int i = 1; i < len; i++) {
        int curr = pre + sum - len * nums[len - i];
        ans = Math.max(ans, curr);
        pre = curr;
    }

    return ans;
}

复杂度分析：

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。

• 空间复杂度：$O(1)$。

方法三： 前缀和 + 滑动窗口

思路与算法：

因为需要旋转数组，可以将 $nums$ 进行复制拼接，得到长度为 $2n$ 的新数组，在新数组上任意一个长度为 $n$ 的滑动窗口都对应了一个旋转数组。

考虑在窗口的滑动过程中，计算结果会如何变化，假设当前我们处理到下标为 $[i, i+n-1]$ 的滑动窗口，当前结果为：

$cur = nums[i] \times 0 + nums[i+1] \times 1 + ... + nums[i+n-1] \times (n-1)$

当窗口往后移动一位，也就是窗口的右端点来到 $i+n$ 的位置，左端点来到 $i+1$ 的位置。

我们需要增加新右端点的值，即增加 $nums[i+n] \times (n-1)$，同时减去旧左端点的值，即减少 $nums[i] \times 0$，然后更新新旧窗口的公共部分 $[i + 1, i + n - 1]$。

不难发现，随着窗口的逐步右移，每一位公共部分的权值系数都会进行减一。

$nums[i+1] \times 1 + nums[i+2] \times 2 + ... + nums[i+n-1] \times (n-1)$

变为

$nums[i+1] \times 0 + nums[i+2] \times 1 + ... + nums[i+n-1] \times (n-2)$

因此，公共部分的差值为 $\sum_{idx=i+1}^{i+n-1}nums[idx]$，我们可以使用前缀和进行优化。

public int maxRotateFunction(int[] nums) {
	int len = nums.length;
	if (len <= 1) {
		return 0;
	}

	int[] sum = new int[2 * len + 1];
	for (int i = 1; i <= 2 * len; i++) {
		sum[i] = sum[i - 1] + nums[(i - 1) % len];
	}

	int ans = 0;
	for (int i = 0; i < len; i++) {
		ans += i * nums[i];
	}

	int curr = ans;
	for (int i = len + 1; i < 2 * len; i++) {
		curr += nums[(i - 1) % len] * (len - 1);
		curr -= sum[i - 1] - sum[i - len];
		ans = Math.max(ans, curr);
	}

	return ans;
}

复杂度分析：

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。

• 空间复杂度：$O(1)$。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗