1. 三分查找
- 场景
- 序列不满足单调增或者单调减
- 但满足局部的单调性
- 即只存在波峰或者只存在波谷
- 求波峰和波谷
- 我们并不字段波峰和波谷在哪里
- 定义域l-r
- 我们在定义域里任取两数lmid，rmid
- 对于
f(lmid)<=f(rmid),说明极大值在 lmid-r - 对于
f(lmid)>=f(rmid),说明极大值在 l - rmid
162. 寻找峰值(三分查找的模板)
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
完整代码
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
// 取lmid为二分点，rmid为lmid+1
let n=nums.length
let l=0
let r=n-1
// nums[-1]=-Infinity
// nums[n]=-Infinity
while(l<r){
let lmid=Math.floor((l+r)/2)
let rmid=lmid+1
// 看最大值在哪一侧
if(nums[lmid]<nums[rmid]){
// 在右侧
l=lmid+1
}else{
r=rmid-1
}
}
// console.log(r)
return r
};
2. 二分答案
- 场景
- 对于一个给定的值，存在>=或者<= 或者满足其他不等式的情况
- 结果是确定的，但直接求解困难
- 我们通过不等式的关系猜测答案，通过二分缩小答案的范围，达到求解的目的
410. 分割数组的最大值
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], m = 2
输出：9
示例 3：
输入：nums = [1,4,4], m = 3
输出：4
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= m <= min(50, nums.length)
完整代码
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var splitArray = function(nums, k) {
// 我们直接求解非常困难
// 如果使用万金油解法，画出状态空间，时间复杂度O(C(n,m))
// 选m次，每次选择，n，n-1，.... n-m
// 时间复杂度爆炸
// 我们从二分的思想
// 对于正解，设为T，那么是否所有的分组的和<=T
// 一般如果能化为这样的一个不等式，就可以尝试二分了
// T我们不知道，但是可以猜测，即nums数组中最大值 -到- nums数组之和
// 这里是不是就转换成了猜数字的问题
let left=0
let right=0
for(let i=0;i<nums.length;i++){
left=Math.max(left,nums[i])
right+=nums[i]
}
const isValid=(T)=>{
let groupSum=0
let groupNum=1
for(let i=0;i<nums.length;i++){
if(groupSum+nums[i]<=T){
groupSum+=nums[i]
}else{
// 不满足，重新分配一组
groupNum++
groupSum=nums[i]
}
}
// k为规定的组数
// 如果大于k，说明不满足
return groupNum<=k
}
while(left<right){
let T=Math.floor((left+right)/2)
// 判断T是否满足所有的组<=T
if(isValid(T)){
right=T
}else{
left=T+1
}
}
return right
};
1482. 制作 m 束花所需的最少天数
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
示例 1：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _] // 只能制作 1 束花
2 天后：[x, _, _, _, x] // 只能制作 2 束花
3 天后：[x, _, x, _, x] // 可以制作 3 束花，答案为 3
示例 2：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。
示例 3：
输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。
示例 4：
输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束
示例 5：
输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
输出：9
提示：
bloomDay.length == n1 <= n <= 10^51 <= bloomDay[i] <= 10^91 <= m <= 10^61 <= k <= n
解题思路
1. 和上题差不多
2. 对于最小的等待天数
3. 连续子数组满足不等式nums[i]<=T
4. 我们求满足不等式的子数组的个数
5. 知道最小的子数组个数满足题意>=m 的最小子数组
完整代码
/**
* @param {number[]} bloomDay
* @param {number} m
* @param {number} k
* @return {number}
*/
var minDays = function(bloomDay, m, k) {
// 特殊情况，花不够
if(m*k>bloomDay.length) return -1
// 该题可能的解 min(bloomDay) - max(bloomDay)
let left=0
let right=0
for(let i=0;i<bloomDay.length;i++){
left=Math.min(left,bloomDay[i])
right=Math.max(right,bloomDay[i])
}
// 判断猜测的day是否满足条件
const isValid=(T)=>{
// 组个数为m
// 每组元素个数为k
// 连续k个的组有几个
let cnt=0
let kCnt=0
for(let i=0;i<bloomDay.length;i++){
if(bloomDay[i]<=T){
cnt++
if(cnt===k){
kCnt++
cnt=0
}
}else{
cnt=0
}
}
return kCnt>=m
}
while(left<right){
let mid=Math.floor((left+right)/2)
if(isValid(mid)){
right=mid
}else{
left=mid+1
}
}
return right
};
1011. 在 D 天内送达包裹的能力
传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例 2：
输入：weights = [3,2,2,4,1,4], days = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
示例 3：
输入：weights = [1,2,3,1,1], days = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
提示：
1 <= days <= weights.length <= 5 * 1041 <= weights[i] <= 500
完整代码(<=target 猜数字类型)
/**
* @param {number[]} weights
* @param {number} days
* @return {number}
*/
var shipWithinDays = function(weights, days) {
// 明显的二分答案
// 最低运载能力我们不知道，但是可以猜测
// max(weights) -- sums(weights)
let left=0
let right=0
for(let i=0;i<weights.length;i++){
left=Math.max(left,weights[i])
right+=weights[i]
}
// 是否满足条件，即运载所有货物的天数是否小于给定天数
const isValid=(T)=>{
let dCnt=1
let wCnt=0
for(let i=0;i<weights.length;i++){
if(wCnt+weights[i]<=T){
wCnt+=weights[i]
}else{
// 第二天运
dCnt++
wCnt=weights[i]
}
}
return dCnt<=days
}
while(left<right){
let mid=Math.floor((left+right)/2)
if(isValid(mid)){
right=mid
}else{
left=mid+1
}
}
return right
};
911. 在线选举
给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。
对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。
在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
实现 TopVotedCandidate 类：
TopVotedCandidate(int[] persons, int[] times)使用persons和times数组初始化对象。int q(int t)根据前面描述的规则，返回在时刻t在选举中领先的候选人的编号。
示例：
输入：
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
输出：
[null, 0, 1, 1, 0, 0, 1]
解释：
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // 返回 0 ，在时刻 3 ，票数分布为 [0] ，编号为 0 的候选人领先。
topVotedCandidate.q(12); // 返回 1 ，在时刻 12 ，票数分布为 [0,1,1] ，编号为 1 的候选人领先。
topVotedCandidate.q(25); // 返回 1 ，在时刻 25 ，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。
topVotedCandidate.q(15); // 返回 0
topVotedCandidate.q(24); // 返回 0
topVotedCandidate.q(8); // 返回 1
提示：
1 <= persons.length <= 5000times.length == persons.length0 <= persons[i] < persons.length0 <= times[i] <= 109times是一个严格递增的有序数组times[0] <= t <= 109- 每个测试用例最多调用
104次q
完整代码(简单二分<=target的最后一个)
/**
* @param {number[]} persons
* @param {number[]} times
*/
var TopVotedCandidate = function(persons, times) {
// 如果不考虑时间复杂度，可以使用前缀和，每个时刻对应一个leader
// this.map=new Map()
// 记录每个时刻的候选人
let top=[]
top[-1]=0
// 记录每个候选人的票数
let map=new Map()
map.set(-1,0)
for(let i=0;i<persons.length;i++){
if(map.has(persons[i])){
map.set(persons[i],map.get(persons[i])+1)
}else{
map.set(persons[i],1)
}
if(map.get(persons[i])>=map.get(top[i-1])){
top[i]=persons[i]
}else{
top[i]=top[i-1]
}
}
console.log(top)
this.persons=top
// this.be=persons
this.times=times
};
/**
* @param {number} t
* @return {number}
*/
TopVotedCandidate.prototype.q = function(t) {
// 即查找<=t 的最后一个times
let left=-1
let right=this.times.length-1
while(left<right){
let mid=Math.floor((left+right+1)/2)
if(this.times[mid]<=t){
left=mid
}else{
right=mid-1
}
}
return this.persons[right]
};
/**
* Your TopVotedCandidate object will be instantiated and called as such:
* var obj = new TopVotedCandidate(persons, times)
* var param_1 = obj.q(t)
*/
875. 爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
示例 1：
输入：piles = [3,6,7,11], h = 8
输出：4
示例 2：
输入：piles = [30,11,23,4,20], h = 5
输出：30
示例 3：
输入：piles = [30,11,23,4,20], h = 6
输出：23
提示：
1 <= piles.length <= 104piles.length <= h <= 1091 <= piles[i] <= 109
完整代码（<=target 的猜数字类型）
/**
* @param {number[]} piles
* @param {number} h
* @return {number}
*/
var minEatingSpeed = function(piles, h) {
// <=T
// 吃香蕉的速度我们不知道，但是可以猜测
// h>=1
// 速度 解空间 1-max(piles[i])
let left=1
let right=0
for(let i=0;i<piles.length;i++){
right=Math.max(right,piles[i])
}
const isValid=(T)=>{
// 我们看吃完所有香蕉所需要的时间
let hours=0
for(let i=0;i<piles.length;i++){
hours+=(Math.floor((piles[i]-1)/T)+1)
}
return hours<=h
}
while(left<right){
let mid=Math.floor((left+right)/2)
if(isValid(mid)){
right=mid
}else{
left=mid+1
}
}
return right
};