题目重点：切成两个非空连续段，各段独立排序，合并后要非降。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 只允许一个切点k，1≤k<n；原数组可重复及为负。
- 两段排序后直接拼接，不是把两段混合归并。
解题路线
- 左段内部和右段内部排序后必合法，唯一风险是跨段边界。边界合法当且仅当max(left)≤min(right)。
- 反向预计算suffix_min，正向维护prefix_max，在每个切点检查一次。这个必要充分条件同时给出正确性证明。
- 无需真的排序。若要求每段内部原顺序保持，则问题换成两个本来有序的连续段，不能复用本合同结论。
手动走一遍
[1,3,2,4]切k=1和3合法：1≤2、3≤4；k=2不合法，因为左最大3>右最小2。[2,2,2]两个切点都合法，比较必须允许相等。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def valid_cuts(a):
n = len(a)
if n < 2:
return []
suffix_min = [0] * n
suffix_min[-1] = a[-1]
for i in range(n - 2, -1, -1):
suffix_min[i] = min(a[i], suffix_min[i + 1])
result, prefix_max = [], a[0]
for k in range(1, n):
prefix_max = max(prefix_max, a[k - 1])
if prefix_max <= suffix_min[k]:
result.append(k)
return result
复杂度
O(n)时间、O(n)后缀数组空间；只求一个最早切点可讨论partition-disjoint的O(1)空间扫描。
易错点与追问
容易失分的边界
- 不要按a[k−1]≤a[k]判断，左端更早可能有更大元素。
- n<2没有两个非空段，结果为空。
继续深挖
- 允许多段时，哪些边界能同时取？
- 只返回第一个合法切点怎样省掉后缀数组并证明扩展左段的规则？
