每日一题-6th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

Leetcode 396. 旋转函数

题干

给定一个长度为 n 的整数数组 nums （nums[i]∈[-100,100]）。假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数 F 为：

F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]

返回 F(0), F(1), ..., F(n-1)中的最大值 。已知生成的测试用例让答案符合 32 位 整数。

注：本人亲测，时间复杂度 $O(n^2)$ 会超时；

示例

示例 1:

输入: nums = [4,3,2,6]
输出: 26
解释:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。

示例 2:

1 2	输入: nums = [100] 输出: 0

思路

遍历法（最容易想到，$O(n^2)$ 时间、$O(1)$ 空间）：数组本身无需旋转，只需遍历 $F(0)\sim F(n-1)$ 的值取最大值即可，如下：

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int len = nums.size(), maxVal = -1e4 * len;
        // 计算F(start)同时取最大值
        for (int start = 0; start < len; ++start) {
            int tmpSum = 0;
            for (int delta = 0; delta < len; ++delta) {
                tmpSum += delta * nums[(start + delta) % len];
            }
            if (maxVal < tmpSum) maxVal = tmpSum;
        }
        return maxVal;
    }
};

评价：测试集中存在大规模样本，$O(n^2)$ 时间完全不够，需要优化

计算简化法（$O(n)$ 时间，$O(1)$ 空间）：考虑不能遍历，只能从数学层面描述 $F(n)$ 的增长规律，以此找出 $F(0)\sim F(n-1)$ 间的最大值。下面研究 $F(n+1)$ 和 $F(n)$ 的关系，会发现两者有类似错位相消的关系：
$\begin{aligned} F(0)&=0\cdot a_0+1\cdot a_1+...+(n-1)\cdot a_{n-1}\\\\ F(1)&=1\cdot a_0+2\cdot a_2+...+(n-1)\cdot a_{n-2}+0\cdot a_{n-1}\\\\ &\cdots\cdots\\\\ F(k)&=k\cdot a_0+(k+1)\cdot a_1+...+(k-1+n)\space\%\space n\cdot a_{n-1}\\ \\ F(k+1)&=(k+1)\cdot a_0+(k+2)\space\%\space n\cdot a_1+...+(k-1+n)\space\%\space n\cdot a_{n-2}+k\cdot a_{n-1}\\ \end{aligned}$
$\Longrightarrow F(k+1)-F(k)=\sum\limits_{exclude\space b_0}a_i-(n-1)b_0$，其中 $b_0$ 是 $(a_{i})_n$ 向右翻转 k+1 次的第一个元素；

$\Longrightarrow F(k+1)-F(k)=\sum\limits_{i}a_i-(n-1)b_0-b_0=\sum\limits_ia_i-na_{n-k-1}\quad Assuming\space that\space k\in[0,n-2]$

故此我们无需遍历整个数组，只需遍历一次，就能获得 $\sum\limits_ia_i$ 信息和 $F(0)$，这样在遍历 $F(1)\sim F(n-1)$ 时的时间复杂度就是 $O(n)$；

实现

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int len = nums.size(), F0 = 0, nsum = 0;
        for (int i = 0; i < len; ++i) {
            nsum += nums[i]; F0 += i * nums[i];
        }
        int maxF = F0, tmpF = F0;
        for (int k = 1; k < len; ++k) {
            tmpF += nsum - len * nums[len - k];
            if (tmpF > maxF) maxF = tmpF;
        }
        return maxF;
    }
};