本文介绍一种基于有限状态机思想的算法，用于准确识别数组中所有连续单调子序列（先降后升或先升后降的转折点），并对每个子序列独立升序排序，避免子序列边界重叠导致的错误。
本文介绍一种基于有限状态机思想的算法，用于准确识别数组中所有连续单调子序列（先降后升或先升后降的转折点），并对每个子序列独立升序排序，避免子序列边界重叠导致的错误。
在处理如 [53, 50, 41, 8, 64, 35, 17, 76, 58, 3, 75, 1, 99, 56, 2] 这类数组时，核心目标是：将每个极大连续单调（严格递减或递增）子段视为一个逻辑单元，并对其内部元素升序排序。关键在于精准切分子序列边界——传统单向扫描易因方向判断滞后而合并相邻段（如将 [76,58,3] 和 [75,1] 错误连成 [76,58,3,75,1]），导致排序结果错位。
问题根源在于原代码仅检测“下降趋势”，且依赖全局最大长度回溯起点，忽略了单调性转折点（peak/valley）才是天然分割符。正确思路是：当序列方向发生反转（如由降变升，或由升变降）时，即为上一子序列的终点和下一子序列的起点。
✅ 正确算法：有限状态机驱动的子序列切分
我们维护两个布尔状态：
- was_up：前一对元素是否上升（x[i-1] < x[i]）
- was_down：前一对元素是否下降（x[i-1] > x[i]）
遍历至第 i 个元素（比较 x[i] 与 x[i+1]）时，计算当前方向 up 和 down。若出现方向翻转——即 (was_up && down) 或 (was_down && up)，说明 i 是上一单调段的末尾索引，应立即对 [ldx, i] 区间升序排序，并重置 ldx = i + 1，清空方向状态。
⚠️ 注意：需在循环结束后补一次排序，处理最后一段（[ldx, end]）。
? Java 实现示例（适配原题需求）
import java.util.*;
public class MonotonicSegmentSort {
public static void sortMonotonicSegments(int[] arr) {
if (arr == null || arr.length <= 1) return;
int ldx = 0; // 当前段起始索引
boolean wasUp = false, wasDown = false;
for (int i = 0; i < arr.length - 1; i++) {
boolean up = arr[i] < arr[i + 1];
boolean down = arr[i] > arr[i + 1];
// 方向反转：上一段结束，触发排序
if ((wasUp && down) || (wasDown && up)) {
Arrays.sort(arr, ldx, i + 1); // 升序排序 [ldx, i]
ldx = i + 1;
wasUp = wasDown = false;
} else {
wasUp = up;
wasDown = down;
}
}
// 排序最后一段
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]
}
}? 关键要点总结
- 不依赖“最长下降段”贪心策略：原方法试图找全局最长下降段再递归，但破坏了局部单调段的完整性；新方法以方向转折为唯一切分依据，符合题目语义（“each sequence within the array”）。
- 严格处理边界：Arrays.sort(arr, from, to) 的 to 是开区间，确保 [ldx, i] 被完整包含。
- 时间复杂度：O(n log k)，其中 k 为各段平均长度；空间复杂度 O(1)（原地排序）。
- 扩展性：若需保留原始段信息（如记录每段长度/类型），可额外维护 List<int[]> segments 在每次排序前收集 [ldx, i]。
该方案彻底解决子序列重叠与错位问题，输出严格匹配预期：[8,41,50,53], [17,35,64], [3,58,76], [1,75], [2,56,99] 拼接后的结果。
