企业官网建设流程全解析

• 科学计算

本文围绕 LeetCode 双周赛 113 期第 1 题「通过右移操作使数组变为递增的最小次数」展开。这是一道经典的「循环移位 + 单调性判定」问题，题解文档 README.md 给出了暴力枚举与分段扫描两种解法，本文将以该文档为骨架，结合 codeforces-go 仓库中的 a.go 实现、a_test.go 测试驱动与 a.txt 测试数据，深入讲解两种方法的原理、复杂度差异与工程化测试方式。读完本文，你将掌握如何用 O(n) 时间判定「一个数组能否通过若干次整体右移变为严格递增」，并能独立完成该题的 Go 实现与本地验证。

题目回顾与核心观察

给定一个整数数组nums，一次「右移」操作将数组整体向右移动一位，最后一个元素移动到首位，即：

[3,4,5,1,2] → [2,3,4,5,1] → [1,2,3,4,5] → ...

问最少需要多少次右移，才能使数组变为严格递增（每个元素严格小于后一个元素）；如果无法做到，返回-1。

题目最关键的一条观察是：右移 n 次后数组会恢复原状。因此，如果存在可行解，所需次数一定落在[0, n-1]这个区间内，最多尝试 n 次即可穷尽所有可能的移位状态。这一观察直接催生了方法一的暴力思路，也为方法二的数学化压缩奠定了基础。

方法一：暴力模拟（O(n²)）

方法一的思路非常直白：不断右移，每次右移前先判断当前数组是否有序。

• 若当前数组已严格递增，直接返回已执行的右移次数；
• 否则继续右移一次，重复上述判断；
• 若循环结束仍无解，返回-1。

由于右移 n 次必然回到初始状态，循环最多执行 n 次，所以答案不可能超出n-1。

Python 实现

文档给出的 Python3 解法利用pairwise逐对比较相邻元素，并借助切片完成右移：

class Solution: def minimumRightShifts(self, nums: List[int]) -> int: for i in range(len(nums)): if all(x < y for x, y in pairwise(nums)): return i nums = [nums[-1]] + nums[:-1] return -1

Go 实现与仓库源码

仓库 a.go 中的minimumRightShifts2是与文档对应的 Go 版本，它复用了 Go 标准库sort.IntsAreSorted做有序性判断，用切片的拼接完成一次右移：

func minimumRightShifts2(a []int) int { for i := 0; i < len(a); i++ { if sort.IntsAreSorted(a) { return i } a = append(a[len(a)-1:], a[:len(a)-1]...) } return -1 }

实现细节值得注意：

• sort.IntsAreSorted(a)判断的是非严格递增（<=），而题目要求严格递增（<）。对于本题数据而言，如果数组存在相邻相等元素，两种判定会得出不同结论——阅读源码时需留意这一点（后续方法二同样采用严格递增的<比较，与题解文档的语义一致）。
• append(a[len(a)-1:], a[:len(a)-1]...)是 Go 中经典的「取尾元素放到头部」右移写法，其底层会触发切片扩容与元素搬移，这也是方法一时间复杂度达到 O(n²) 的原因之一。

复杂度分析

• 时间复杂度：O(n²)。最坏情况下要右移 n-1 次，每次右移与有序性判断都需 O(n) 时间。
• 空间复杂度：O(n)。每次右移都会创建新的切片（Python 切片的拼接同样产生新列表）。

暴力方法代码极短、正确性一目了然，非常适合作为对拍基准（参见后文测试小节）；但它无法通过大规模数据，需要进一步优化。

方法二：至多两段递增子数组（O(n)）

方法二不再模拟移动，而是直接对原数组做结构分析，其核心洞察是：

右移的本质是「把数组尾部的一段挪到头部」。因此，目标数组若严格递增，则原数组nums必须至多由两段严格递增子数组拼接而成（第二段恰好是原数组尾部被移到头部的那段）。

具体而言，右移 k 次后的数组为nums[n-k..n-1] + nums[0..n-k-1]。要让它整体严格递增，必须同时满足：

1. 第一段nums[n-k..n-1]内部严格递增；
2. 第二段nums[0..n-k-1]内部严格递增；
3. 段与段之间的边界也要衔接正确：第一段的最后一个元素（即原数组的最后一个元素nums[n-1]）必须小于第二段的第一个元素（即nums[0]）。

而nums中两段递增子数组的划分点只有一个候选，就是「第一个不满足严格递增的相邻位置」。于是可以把「找最少右移次数」压缩为一次线性扫描：

1. 从下标 1 开始向后扫描，直到遇到nums[i-1] >= nums[i]，此时得到第一段，其长度记为i。
2. 若第一段长度就是n（整个数组已经严格递增），返回0。
3. 若nums[0] < nums[n-1]，说明尾部段接在头部段之前无法形成衔接（首元素不够大），返回-1。
4. 否则令mid = i，从i+1继续扫描第二段。
5. 若第二段之后又出现不递增的位置（存在第三段），返回-1。
6. 若一切顺利，第二段长度为n - mid，这正是需要右移的次数，返回它。

Python 实现

文档给出的 Python3 版本完整实现了上述扫描逻辑：

class Solution: def minimumRightShifts(self, nums: List[int]) -> int: i, n = 1, len(nums) while i < n and nums[i - 1] < nums[i]: i += 1 if i == n: return 0 if nums[0] < nums[-1]: return -1 mid = i i += 1 while i < n and nums[i - 1] < nums[i]: i += 1 if i < n: return -1 return n - mid

Go 实现与仓库源码

仓库 a.go 中的minimumRightShifts与文档完全一致，是本题在仓库中的最终提交版本：

func minimumRightShifts(a []int) int { i, n := 1, len(a) for i < n && a[i-1] < a[i] { i++ } if i == n { return 0 } if a[0] < a[n-1] { return -1 } mid := i i++ for i < n && a[i-1] < a[i] { i++ } if i < n { return -1 } return n - mid }

对照文档算法步骤可以看得更清楚：

• 第一个for循环对应算法第 1 步，找到第一段结尾下标i；
• i == n对应第 2 步，整段已有序，返回 0；
• a[0] < a[n-1]对应第 3 步的边界衔接检查；
• mid := i; i++跳过断点后，第二个for循环扫描第二段，对应第 4、5 步；
• 循环结束若i < n，说明还有第三段，返回-1；
• 否则第二段长度为n - mid，即最少右移次数。

与暴力版minimumRightShifts2不同的是，此版本全程不修改数组、不分配新内存，两个指针各至多遍历一次数组，因此达到 O(n) 时间、O(1) 空间的理想复杂度。

为什么返回n - mid就是最少次数

右移 k 次后，数组变为a[n-k..n-1] + a[0..n-k-1]。要构造出严格递增序列，尾部段必须整体挪到头部，且尾部段的起点必须恰好是第二段的起点mid。第二段的长度为n - mid，这正是需要移动的元素个数，即最少右移次数。例如：

[3,4,5,1,2]

扫描第一段得到i = 3（元素 3,4,5），a[0]=3 > a[4]=2满足衔接，mid = 3，第二段为[1,2]，长度n - mid = 2，因此右移 2 次得到[1,2,3,4,5]，答案 2。

复杂度分析

• 时间复杂度：O(n)，其中 n 为nums的长度。两段扫描各遍历数组一次，整体仍是线性。
• 空间复杂度：O(1)，仅使用常数个变量。

仓库实测：测试数据与本地验证

为了印证解法正确性，仓库为本题配套了完整的测试设施。

测试用例数据

测试数据文件 a.txt 收录了 3 组输入/期望输出对：

[3,4,5,1,2] 2 [1,3,5] 0 [2,1,4] -1

三组数据恰好覆盖了三种典型情形：

• [3,4,5,1,2]→ 需要右移 2 次，属于「两段递增 + 尾部接头部」的正常解；
• [1,3,5]→ 本身已严格递增，右移 0 次；
• [2,1,4]→ 第一段为[2]，a[0]=2 > a[2]=4满足衔接，但第二段扫描时在1->4处满足递增，随后i已到n…… 实际检查会发现第一段是[2]（i=1），a[0]=2 < a[2]=4，衔接失败，返回-1。

测试驱动机制

测试文件 a_test.go 由copypasta/template/leetcode/generator_test.go自动生成，其核心只有一行调用：

func Test_a(t *testing.T) { targetCaseNum := 0 // -1 if err := testutil.RunLeetCodeFuncWithFile(t, minimumRightShifts, "a.txt", targetCaseNum); err != nil { t.Fatal(err) } }

targetCaseNum的含义值得说明：0表示运行全部用例；负数-1表示只运行最后一个用例（用于调试单条数据）。在 leetcode.go 的RunLeetCodeFuncWithFile中，文件按「每fNumIn + fNumOut行一组」解析：本题函数只有一个入参、一个返回值，因此每 2 行构成一组输入/期望输出，经反射逐组喂给被测函数并自动比对。

仓库测试框架还具备超时检测能力：当targetCaseNum == 0时，leetcode.go 的isTLE会为每次调用设置定时器，超时即判定为「超时」用例并输出输入数据，方便定位性能瓶颈。这意味着即使把暴力版minimumRightShifts2挂进测试，也能在随机数据上直观暴露其 O(n²) 的劣势。

总结与延伸

两种方法都基于同一个观察：右移 n 次回到原数组，答案至多为 n-1。方法一胜在简洁直观，适合作为暴力基准；方法二把「旋转排序」问题转化为「至多两段递增子数组 + 端点衔接」的线性结构判断，是面试与竞赛中的推荐写法。仓库 a.go 同时保留了两种实现，配合 a.txt 与 testutil 测试框架，可随时通过go test ./leetcode/biweekly/113/a完成本地验证，是算法题「题解 + 实现 + 测试」三位一体组织方式的一个典型范例。

• 科学计算