首页 > 编程语言 >数组单调子序列识别与排序（升序/降序）

数组单调子序列识别与排序（升序/降序）

来源：互联网 2026-07-12 08:05:07

采用有限状态机检测方向转折点，将数组切分为连续单调子段，每段独立进行升序排序。通过维护升降状态，在方向反转时确定子段边界并排序，避免了传统方法因边界误判导致的段合并与排序错误，实现精准的单调子序列识别与排序。

来，直接上干货——核心思路是用有限状态机来切分序列，让每个连续单调子段（无论是先降后升，还是先升后降）都能被精准识别，然后各自独立做升序排序，彻底避免边界重叠导致的错乱。我们实际面对的问题是这样的：拿一个数组举例，比如 [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]`）。

Ja va 实现示例

import ja va.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`，在每次排序前把 `[ldx, i]` 收集起来。这个方案彻底解决了子序列重叠与错位的问题，输出结果完全匹配预期：`[8,41,50,53]`, `[17,35,64]`, `[3,58,76]`, `[1,75]`, `[2,56,99]`，拼接起来就是最终结果。

侠游戏发布此文仅为了传递信息，不代表侠游戏网站认同其观点或证实其描述