题解 | 最短排序

import java.util.*;


public class ShortSubsequence {
    public int findShortest(int[] A, int n) {
        if (n <= 1) return 0;

        int left = 0, right = n - 1;

        // 找到第一个不满足升序的元素
        while (left < n - 1 && A[left] <= A[left + 1]) {
            left++;
        }

        // 如果整个数组是有序的
        if (left == n - 1) return 0;

        // 找到最后一个不满足升序的元素
        while (right > 0 && A[right] >= A[right - 1]) {
            right--;
        }

        // 在[left, right]之间找到最小值和最大值
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = left; i <= right; i++) {
            if (A[i] < min) min = A[i];
            if (A[i] > max) max = A[i];
        }

        // 扩展left和right边界
        while (left > 0 && A[left - 1] > min) {
            left--;
        }
        while (right < n - 1 && A[right + 1] < max) {
            right++;
        }

        return right - left + 1;  // 返回需要排序的最短子数组的长度
    }

    public static void main(String[] args) {
        ShortSubsequence ss = new ShortSubsequence();
        int[] A = {1, 5, 3, 4, 2, 6, 7};
        int result = ss.findShortest(A, A.length);
        System.out.println(result);  // 输出 4
    }
}

class ShortSubsequence {
public:
    int findShortest(vector<int>& A) {
        int n = A.size();
        if (n <= 1) return 0;

        int left = 0, right = n - 1;

        // 找到第一个不满足升序的元素
        while (left < n - 1 && A[left] <= A[left + 1]) {
            left++;
        }

        // 如果整个数组是有序的
        if (left == n - 1) return 0;

        // 找到最后一个不满足升序的元素
        while (right > 0 && A[right] >= A[right - 1]) {
            right--;
        }

        // 在[left, right]之间找到最小值和最大值
        int min = INT_MAX;
        int max = INT_MIN;
        for (int i = left; i <= right; i++) {
            if (A[i] < min) min = A[i];
            if (A[i] > max) max = A[i];
        }

        // 扩展left和right边界
        while (left > 0 && A[left - 1] > min) {
            left--;
        }
        while (right < n - 1 && A[right + 1] < max) {
            right++;
        }

        return right - left + 1;  // 返回需要排序的最短子数组的长度
    }
};

# -*- coding: utf-8 -*-

class ShortSubsequence:
    def findShortest(self, A, n):
        if n <= 1:
            return 0

        left, right = 0, n - 1

        # 找到第一个不满足升序的元素
        while left < n - 1 and A[left] <= A[left + 1]:
            left += 1

        # 如果整个数组是有序的
        if left == n - 1:
            return 0

        # 找到最后一个不满足升序的元素
        while right > 0 and A[right] >= A[right - 1]:
            right -= 1

        # 在[left, right]之间找到最小值和最大值
        min_val = float('inf')
        max_val = float('-inf')
        for i in xrange(left, right + 1):
            if A[i] < min_val:
                min_val = A[i]
            if A[i] > max_val:
                max_val = A[i]

        # 扩展left和right边界
        while left > 0 and A[left - 1] > min_val:
            left -= 1
        while right < n - 1 and A[right + 1] < max_val:
            right += 1

        return right - left + 1  # 返回需要排序的最短子数组的长度