题目链接:https://leetcode-cn.com/problems/sub-sort-lcci/
思路如下:
从左往右看,正序应该是逐渐变大,最右逆序对所在的位置就是我们要求的右边界。
从右往左看,正序应该是逐渐变小,最左逆序对所在的位置就是我们要求的左边界。
求右边界和求左边界的过程是对称的。
从左往右扫描,记录扫描过的数中的最大值 max
,如果发现当前值小于最大值,则记录它的位置 right
,最终 right
保存的就是我们要求的右边界。
从右往左扫描,记录扫描过的数中的最小值 min
,如果发现当前值大于最小值,则记录它的位置 left
,最终 left
保存的就是我们要求的左边界。
Java代码如下:
class Solution {
public int[] subSort(int[] array) {
if (array.length == 0) return new int[] {-1, -1};
int max = array[0]; // 记录扫描过的数中的最大值
int right = -1; // 记录最右逆序对所在的位置
for (int i = 1; i < array.length; i++) {
int t = array[i];
if (t < max) {
right = i;
} else {
max = t;
}
}
if (right == -1) return new int[] {-1, -1};
int min = array[array.length - 1]; // 记录扫描过的数中的最小值
int left = -1; // 记录最左逆序对所在的位置
for (int i = array.length - 2; i >= 0; i--) {
int t = array[i];
if (t > min) {
left = i;
} else {
min = t;
}
}
return new int[] {left, right};
}
}
C++代码如下: