部分排序
- 难度：Medium
- 题目链接：https://leetcode-cn.com/problems/sub-sort-lcci/
题目描述
给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
示例：
输入： [1,2,4,7,10,11,7,12,6,7,16,18,19] 输出： [3,9]
提示：
0 <= len(array) <= 1000000
解法：
如果一个数的后面存在比它小的数，那么它必然需要被排序。如果一个数的前面存在比它大的数，这个数也必然要被排序。
因此，从右向左遍历，记录下最小值，如果某个 arr[i] 大于最小值，此数就在排序范围内。遍历完成后，能得到需要排序的区间的左边界。
同样的，从左到右遍历，记录下最大值，如果某个 arr[i] 小于最大值，此数就需要被排序。遍历完成后，得到区间的右边界。
class Solution {
public:
vector<int> subSort(vector<int>& arr) {
int left = -1, right = -1;
int max_n = INT_MIN, min_n = INT_MAX;
for(int i=0;i<arr.size();i++){
if(arr[i] >= max_n){
max_n = arr[i];
}else{
right = i;
}
}
for(int i=arr.size()-1;i>=0;i--){
if(arr[i] <= min_n){
min_n = arr[i];
}else{
left = i;
}
}
return {left, right};
}
};