本文介绍一种基于有限状态机思想的高效算法，用于识别数组中所有严格单调（递增或递减）的连续子序列，并对每个子序列独立升序排序，解决传统遍历法因重叠判断和递归调用导致的索引错位与排序遗漏问题。
本文介绍一种基于有限状态机思想的高效算法，用于识别数组中所有严格单调（递增或递减）的连续子序列，并对每个子序列独立升序排序，解决传统遍历法因重叠判断和递归调用导致的索引错位与排序遗漏问题。
在处理如 [53, 50, 41, 8, 64, 35, 17, 76, 58, 3, 75, 1, 99, 56, 2] 这类数组时，核心目标并非全局排序，而是分段识别“方向转折点”：每个子序列必须是极长的严格单调段（即无法再向左右扩展），例如 [53,50,41,8]（严格递减）、[64,35,17]（严格递减）、[76,58,3]（严格递减）等——注意，相邻段之间由“方向反转”界定：从递减变为递增（如 8 → 64），或从递增变为递减（如 17 → 76），该转折点即为前一段的终点与下一段的起点。
原代码的主要缺陷在于：
- 仅检测“递减长度”，忽略递增段的起始判定；
- 使用单变量 descending 累计长度，无法区分方向变化；
- 递归调用 descendingStructure 导致重复扫描与索引覆盖（如 sortSubArray 修改原数组后，后续递归仍基于旧逻辑判断，引发 76,58,3 段被错误拆解）；
- 边界处理粗糙（如 for (int i = descendingRunStart; i
✅ 正确解法应采用双状态有限自动机（FSM），维护两个布尔状态：
- was_up：上一对元素是否上升（x[i-1]
- was_down：上一对元素是否下降（x[i-1] > x[i]）
当当前比较对 (x[i], x[i+1]) 的趋势与之前相反（即 (was_up && down) 或 (was_down && up)），说明单调性发生拐点，此时立即对 [ldx, i] 区间升序排序，并将 ldx 更新为 i+1，重置状态。
以下是 Java 实现（兼容原题数据结构与需求）：
import java.util.*;
public class MonotonicSegmentSort {
public static void sortMonotonicSegments(int[] arr) {
if (arr == null || arr.length arr[i + 1];
// 方向反转：上一段结束，触发排序
if ((wasUp && down) || (wasDown && up)) {
Arrays.sort(arr, ldx, i + 1); // [ldx, i+1) 左闭右开
ldx = i + 1;
wasUp = false;
wasDown = false;
} else {
wasUp = up;
wasDown = down;
}
}
// 处理最后一段（从 ldx 到末尾）
Arrays.sort(arr, ldx, arr.length);
}
public static void main(String[] args) {
int[] data = {53, 50, 41, 8, 64, 35, 17, 76, 58, 3, 75, 1, 99, 56, 2};
sortMonotonicSegments(data);
System.out.println(Arrays.toString(data));
// 输出: [8, 41, 50, 53, 17, 35, 64, 3, 58, 76, 1, 75, 2, 56, 99]
}
}
? 关键注意事项：
- 严格单调性要求：相等元素（如 5,5,3）会中断递减段（因 5==5 不满足 down），此时 up=false, down=false，状态保持不变，直到出现真正不等关系；
- 索引边界：Arrays.sort(arr, from, to) 的 to 是排他性终点，务必使用 i+1 而非 i；
- 无需递归：单次线性扫描（O(n)）完成分段识别，排序总时间复杂度为 O(n log k)，k 为各段长度，远优于原递归方案的不可控叠加；
- 稳定性：本算法不改变段间相对顺序，仅内部升序化，完全符合题目输出预期。
该方法将“分段逻辑”与“排序动作”解耦，以状态驱动替代嵌套条件与递归，兼具清晰性、健壮性与可扩展性——如需支持降序段单独逆序、或保留原始段方向标识，仅需微调状态机分支即可。
