题解 | 最小调整有序

#include <vector>
class Rearrange {
    vector<int> findSegment_extra(const vector<int>&A){
        if(A.size()<2) return {0,0};
        int left = A.size()-1, right=0;
        int left_max = A[0], right_min = A.back();
        for(int i=0;i<A.size();++i){
            if(A[i] <left_max){
                right=i;
                continue;
            }
            left_max = A[i];
        }
        for(int i=A.size()-1;i>=0;--i){
            if(A[i] > right_min) {
                left = i;
                continue;
            }
            right_min = A[i];
        }
        if(left >= right) return {0,0};
        return {left, right};
    }
  public:
    vector<int> findSegment(vector<int> A, int n) {
        // write code here
        if (n < 2) return {0, 0};
        vector<int> neg_A;
        for(auto a:A){
            neg_A.emplace_back(-a);
        }
        vector<int> res1 = findSegment_extra(A);
        vector<int> res2 = findSegment_extra(neg_A);
        if(res1[1] - res1[0] > res2[1] - res2[0] ){
            return res2;
        }
        return res1;
    }
};