目录
为什么模板要取 while( l < r),而不是while( l <= r)?
while循环结束条件是l >= r,但为什么二分结束时我们优先取r而不是l?
.....................................完善中...............................................
单调区间(非绝对单调,可有相等值)
数组:满足随机存取
时间复杂度O(lonN)
- // 函数 f 是关于自变量 x 的单调函数
- int f(int x) {
- // ...
- }
-
- // 主函数,在 f(x) == target 的约束下求 x 的最值
- int solution(int[] nums, int target) {
- if (nums.length == 0) return -1;
- // 问自己:自变量 x 的最小值是多少?
- int left = ...;
- // 问自己:自变量 x 的最大值是多少?
- int right = ... + 1;
-
- while (left < right) {
- int mid = left + (right - left) / 2;
- if (f(mid) == target) {
- // 问自己:题目是求左边界还是右边界?
- // ...
- } else if (f(mid) < target) {
- // 问自己:怎么让 f(x) 大一点?
- // ...
- } else if (f(mid) > target) {
- // 问自己:怎么让 f(x) 小一点?
- // ...
- }
- }
- return left;
- }
- class Solution {
- public int[] searchRange(int[] nums, int target) {
- //预先判断
- if(nums.length == 0) return new int[]{-1, -1};
-
- //寻找左边界(模板1)
- int l = 0, r = nums.length - 1;
- while(l < r){
- int mid = (l + r) / 2;
- if(nums[mid] >= target) r = mid;
- else l = mid + 1;
- }
- if(nums[r] != target) return new int[]{-1, -1};
- int L = r;
-
- //寻找右边界(模板2)
- l = 0; r = nums.length-1;
- while(l < r){
- int mid = (l + r + 1) / 2; //向上取整,l与r相邻时死循环
- if(nums[mid] <= target) l = mid;
- else r = mid - 1;
- }
-
- //退出while循环后结果优先存储在r中
- //有左边界就一定会有右边界,这里直接返回不用再if判断
- return new int[]{L, r};
- }
- }
模板1和模板2的差别:
在于等号是和大于在一起还是小于在一起,以左边界举例的话就是每次边界收缩时 l指针mid+1左侧的mid一定是小于target的,这就保证了循环结束时 L指针的左侧必定和自己相异
求左边界问题用模板2:如果左边界l要更新为 l = mid,此时我们就要使用模板2,让 mid = (l + r + 1)/ 2,否则while会陷入死循环。
右边界问题用模板1:如果左边界l更新为l = mid + 1,此时我们就使用模板1,让mid = (l + r)/2。
本质上取l < r和 l <= r是没有任何区别的,如果取l <= r,只需要修改对应的更新区间即可。
二分的while循环的结束条件是l >= r,所以在循环结束时l有可能会大于r,此时就可能导致越界,因此,基本上二分问题优先取r都不会翻车。
- class Solution {
- public int triangleNumber(int[] nums) {
- Arrays.sort(nums);
- int n = nums.length;
- int res = 0;
- for (int i = 0; i < n - 2; ++i) {
- for (int j = i + 1; j < n - 1; ++j) {
- int s = nums[i] + nums[j];
- //寻找第一个比两边之和大的元素,相当于找右边界的二分查找
- int l = j + 1, r = n - 1; //确定查找范围[j+1, n-1]
- while (l < r) {
- int mid = l + r + 1 >>> 1; //右边界问题,反之l与r相邻时死循环
- if (nums[mid] < s) l = mid; //往右收缩
- else r = mid - 1; //往左收缩
- }
- if (nums[r] < s) { //r与=号绑定,最终r停在右边界
- res += r - j;
- }
- }
- }
- return res;
- }
- }
双指针法:
首先对数组排序。
固定最长的一条边,运用双指针扫描
如果 nums[l] + nums[r] > nums[i],同时说明 nums[l + 1] + nums[r] > nums[i], ..., nums[r - 1] + nums[r] > nums[i],满足的条件的有 r - l 种,r 左移进入下一轮。
如果 nums[l] + nums[r] <= nums[i],l 右移进入下一轮。
枚举结束后,总和就是答案。
时间复杂度为 O(n^2)
- //双指针解法
- class Solution {
- public int triangleNumber(int[] nums) {
- Arrays.sort(nums);
- int n = nums.length;
- int res = 0;
- for (int i = n - 1; i >= 2; --i) {
- int l = 0, r = i - 1;
- while (l < r) {
- if (nums[l] + nums[r] > nums[i]) {
- res += r - l;
- --r;
- } else {
- ++l;
- }
- }
- }
- return res;
- }
- }
- class Solution {
- public int minEatingSpeed(int[] piles, int h) {
- //确定速度范围,left需要设置为1,最少一小时吃一根香蕉
- int left = 1, right = 1;
- for (int pile : piles) {
- right = Math.max(right, pile);
- }
-
- //二分左边界问题
- while(left < right) {
- int mid = left + (right - left) / 2;
- int count = 0;
- for(int pile : piles) {
- count += (pile - 1) / mid + 1; //向上取整
- }
- if(h >= count) right = mid;
- else left = mid + 1;
- }
- return left;
- }
- }
- class Solution {
- public int shipWithinDays(int[] nums, int days) {
- //确定二分范围(船运载能力的范围)
- int l = Arrays.stream(nums).max().getAsInt(); //包裹不能拆分,最少运送最大包裹的重量
- int r = Arrays.stream(nums).sum(); //所有包裹的重量和
-
- //二分查找左边界问题
- while(l < r){
- int mid = l + (r - l) / 2;
-
- //相当于check()函数
- int day = 1;
- int sum = 0;
- for(int num : nums){
- if(sum + num > mid){
- day++;
- sum = 0;
- }
- sum += num;
- }
-
- //二分查找部分
- if(days >= day){
- r = mid;
- }else{
- l = mid + 1;
- }
- }
- return r;
- }
- }