在 Leetcode (opens new window) 的刷题过程中,我们总会遇到这样一类题:
- 没有思路下手
- 暴力方法破解(看了题目分类一头雾水)
- 一看题解,直呼OMG,秒
这不禁让我想起上初高中的时光,要想取得高(满)分,这就要求我们看见题目,就能找出题眼之所在。
遂有此文,以供参考。
977. 有序数组的平方 - E (opens new window)
这道题就很有意思啦.对于有经验的同学,有序数组可以算是一个题眼,毕竟可以考虑用二分查找。不过也仅限于此,
如果你不能有更深入的思考并得到最大值只可能出现在两端(题眼)。Game Over.
最大值只可能出现在数组的两端 ----> 双指针。
class Solution {
public int[] sortedSquares(int[] nums) {
if(nums == null || nums.length == 0){
return nums;
}
int start = 0;
int end = nums.length - 1;
// 因为每次拿到的都是最大值,所以只能从后往前赋值
int index = nums.length - 1;
while(start <= end){
int s1 = nums[start] * nums[start];
int s2 = nums[end] * nums[end];
if(s1 > s2){
nums[index--] = s1;
start ++;
}else{
nums[index--] = s2;
end --;
}
}
return nums;
}