终于做出来了，这题用来刷掉三哥效果最好
public class Solution {
public boolean minSquaredSmallerThanMax(int[] nums) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
return (long) min * min < max;
}
public int minDelectionFromFront(int[] nums) {
if(minSquaredSmallerThanMax(nums)) {
return 0;
}
int len = nums.length;
double[] sqrts = new double[len];
for (int i = 0; i < len; i++) {
sqrts[i] = nums[i] >= 0 ? Math.sqrt(nums[i]) : Double.MIN_VALUE;
}
double[] rightMaxSqrt = new double[len];
int[] rightMin = new int[len];
for (int i = len - 1; i >= 0; i--) {
if (i == len - 1) {
rightMaxSqrt[i] = sqrts[len - 1];
rightMin[i] = nums[len - 1];
} else {
rightMaxSqrt[i] = Math.max(rightMaxSqrt[i + 1], sqrts[i]);
rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
}
}
//System.out.println("rightMaxSqrt = " + Arrays.toString(
rightMaxSqrt));
//System.out.println("rightMin = " + Arrays.toString(rightMin));
for (int i = 0; i < len; i++) {
if (nums[i] == rightMin[i] && Math.abs(nums[i]) < rightMaxSqrt[i
]) {
return i;
}
}
return -1;
}
public int minDelectionFromBothEnds(int[] nums) {
if(minSquaredSmallerThanMax(nums)) {
return 0;
}
int len = nums.length;
double[] sqrts = new double[len];
for (int i = 0; i < len; i++) {
sqrts[i] = nums[i] >= 0 ? Math.sqrt(nums[i]) : Double.MIN_VALUE;
}
//j >= i
double[][] maxSqrt = new double[len][len];
//j >= i
int[][] min = new int[len][len];
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
if (i == j) {
maxSqrt[i][j] = sqrts[i];
min[i][j] = nums[i];
} else {
maxSqrt[i][j] = Math.max(maxSqrt[i + 1][j], sqrts[i]);
min[i][j] = Math.min(min[i + 1][j], nums[i]);
}
}
}
//print("maxSqrt", maxSqrt);
//print("min", min);
int res = Integer.MAX_VALUE;
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
if(
(nums[j] == min[i][j] && Math.abs(nums[j]) < maxSqrt[i][j])
||
(nums[i] == min[i][j] && Math.abs(nums[i]) < maxSqrt[i][j])
) {
res = Math.min(res, len - (j - i + 1));
}
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
public static void main(String[] args) {
test(new int[] {-9, -8, -7, 4, 25, -11, -20}, false, -1, 5);
test(new int[] {-9, -8, -7, 4, 25, -11, -2}, false, -1, 5);
test(new int[] {-9, -8, -7, 4, 25, -1, -2}, false, -1, 3);
test(new int[] {-9, -8, -7, 4, 25, -1}, false, -1, 3);
test(new int[] {-7, 4, 25}, false, 1, 1);
test(new int[] {-9, -8, -7, 4, 25}, false, 3, 3);
test(new int[] {-49, 1, 4, -1}, false, -1, 1);
test(new int[] {-7, 1, 2, -1}, false, -1, 1);
test(new int[] {-9, 5, -8, -7, 2}, false, -1, -1);
test(new int[] {-9, 3, 2, -8, -7, 5}, false, -1, -1);
test(new int[] {-9, 2, -8, -7, 5}, false, -1, -1);
test(new int[] {-9, 2, -8, -7, 2, 5}, false, 4, 4);
test(new int[] {-9, -8, -7, 2, 5}, false, 3, 3);
test(new int[] { -7, 2, 5}, false, 1, 1);
test(new int[] { 9, -7, 2, 5}, false, 2, 2);
test(new int[] { 1, 2, 3, 4 }, true, 0, 0);
test(new int[] { 5 }, false, -1, -1);
test(new int[] { 1 }, false, -1, -1);
test(new int[] { 5, 1, 3 }, true, 0, 0);
test(new int[] { 1, 1, 1 }, false, -1, -1);
test(new int[] { 5, 3, 1 }, true, 0, 0);
test(new int[] { 2, 5, 3, 1 }, true, 0, 0);
test(new int[] { -2 }, false, -1, -1);
test(new int[] { 1, 5, 3 }, true, 0, 0);
}
private static void test(int[] nums, boolean expectedRes1, int
expectedMinDelectionFromFront, int expectedTakenEnds) {
System.out.println("when nums = " + Arrays.toString(nums));
boolean actualRes1 = soln.minSquaredSmallerThanMax(nums);
int actualMinDelectionFromFront = soln.minDelectionFromFront(nums);
int actualTakenEnds = soln.minDelectionFromBothEnds(nums);
if(actualRes1 != expectedRes1) {
System.err.println("actualRes1 = " + actualRes1 + ", while
expected result = " + expectedRes1);
} else if(actualMinDelectionFromFront !=
expectedMinDelectionFromFront) {
System.err.println("actualMinDelectionFromFront = " +
actualMinDelectionFromFront + ", while expected result = " +
expectedMinDelectionFromFront);
} else if(actualTakenEnds != expectedTakenEnds) {
System.err.println("Error. actualTakenEnds = " + actualTakenEnds
+ ", while expected result = " + expectedTakenEnds);
} else {
System.out.println("Test case passed");
}
System.out.println("==============");
}
static Solution soln = new Solution();
void print(String s, int[][] matrix) {
System.out.println(s + " = ");
for(int[] row : matrix) {
System.out.println(Arrays.toString(row));
}
}
void print(String s, double[][] matrix) {
System.out.println(s + " = ");
for(double[] row : matrix) {
System.out.println(Arrays.toString(row));
}
}
}
