BinarySearch_3_单调性应用问题的二分搜索

Algorithm
Created At :
  1. 单调性应用问题的二分搜索
  2. 875.爱吃香蕉的珂珂
  3. 1011.在D天内送达包裹的能力
  4. 1482.制作 m 束花所需的最少天数
  5. 1231.分享巧克力
  6. 贪心/DP+二分查找
  7. 1802.有界数组中指定下标处的最大值

单调性应用问题的二分搜索

更一般地, 什么问题可以用二分搜索解决?
1.从题目中抽象出一个自变量x, 一个关于x的函数f(x), 以及一个目标值target
2.其中x, f(x), target需要满足以下条件
(i). f(x)必须是在x上的单调函数, 单调增或者单调减都可以, 如果是单调增, 搜索两个子区间和之前的左侧或右侧边界二分搜索的区间更新条件是类似的
(ii). 如果是单调递减, 那么就需要具体去想一下怎么去更新搜索区间, 其实就是将之前默认的递增数组的二分搜索更新条件倒置一下
(iii). 题目是想让我们搜索 f(x) == target时的 x 值

举一个最简单的例子就是给定有序数组 nums 以及一个目标元素 target, 请你计算在数组中的索引位置, 如果有多个元素, 就返回最小的索引; 也就是[搜索左侧边界]这个基础题型; 数组中的索引可以认为是自变量x, 函数关系 f(x) 就可以这么设定

int f(int x, vector<int>& nums) {
  return nums[x];
}

这个函数f就是在访问数组nums, 然后算法完整的代码框架如下

int f(int x, vector<int>& nums) {
  return nums[x];
}
int lowBound(vector<int>& nums, int target) {
  if (nums.size() == 0) {
    return -1;
  }
  int low = 0;
  int high = nums.size();
  while (low < high) {
    int mid = low + (high - low) / 2;
    int fNum = f(mid, nums);
    if (fNum == target) {
      high = mid;
    } else if (fNum < target) {
      low = mid + 1;
    } else if (fNum > target) {
      high = mid;
    }
  }
  return low;
}

更一般地, 我们在解决具体的算法问题的时候, 需要思考的是 

// 函数 f 是关于自变量x的单调函数
int f(int x) {
  // ...
}
int binarySearch(vector<int>& nums, int target) {
  // 问自己: 自变量x的最小值应该是多少
  int low = minX;
  // 问自己: 自变量x的最大值应该是多少
  int high = maxX + 1;
  while (low < high) {
    int mid = low + (high - low) / 2;
    int fNum = f(mid, nums);
    if (fNum == target) {
      // 问自己 题目是要找左边界还是右边界
    } else if (fNum < target) {
      // 问自己: 怎么能让f(x)大一点?
    } else if (fNum > target) {
      // 问自己: 怎么能让f(x)小一点?
    }
  }
  return low;
}

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 <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9

分析:
1.理解题意: 这道题就是说找一个最小的速度吃香蕉, 恰好满足这个小时的要求; 比如 piles = [3,6,7,11], 在速度为 4 的情况下吃的依次的香蕉堆数为 [1,2,2,3,3,4,4,4] (idx从1开始), 如果是速度为 3, 那么 8 小时吃不完; 如果速度是5那么就是 [1,2,2,3,3,4,4,4]; 我们目标是找这个最小的速度也就是 4<5
2.吃香蕉的速度和时间是一个单调函数的关系, 具体来说是个单调递减的函数关系, x 为吃香蕉的速度, 需要 f(x) 小时吃完所有的香蕉; 定义速度为 x 时, 需要 f(x) 小时吃完所有香蕉这件单调的事情为 

// 定义吃香蕉的速度为x时, 需要f(x)小时吃完所有的香蕉
// f(x) 随着x的增加单调递减
int f(vector<int>& piles, int x) {
  int hours = 0;
  for (int& num : piles) {
    hours += num / x;
    if (num % x > 0) {
      ++hours;
    }
  }
  return hours;
}

3.找到 x 取值范围的作为二分搜索的搜索区间, 也就是确定初始的 low 和 high 的操作: 在这道题里面, 最小速度就是 1, 最大速度应该是 piles[i] 的最大值, 因为每小时最多吃1堆香蕉; 所以high可以被设置为*max_element(piles.begin(), piles.end()); 但本题目里面给出 piles[i]的范围, 那么直接可以按照上限去进行搜索 

class Solution {
 public:
  int f(vector<int>& piles, int x) {
    int hours = 0;
    for (int& num : piles) {
      hours += num / x;
      if (num % x > 0) {
        ++hours;
      }
    }
    return hours;
  }
  int minEatingSpeed(vector<int>& piles, int h) {
    int low = 1;
    int high = 1000000000 + 1;
    while (low < high) {
      int mid = low + (high - low) / 2;
      int midNum = f(piles, mid);
      if (midNum == h) {
        high = mid;
      } else if (midNum < h) {
        high = mid;
      } else if (midNum > h) {
        low = mid + 1;
      }
    }
    return low;
  }
};

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, 并且是需要最少的运力, 也就是搜索左侧边界的一个二分搜索
2.这里面的运载能力可以抽象成 x, 需要天数可以抽象成 f(x), 运载能力和需要天数是一个单调递减的关系 

// 在运力为x的情况下, 需要的天数为f(x)
int f(vector<int>& weights, int x) {
  int days = 0;
  for (int i = 0; i < weights.size(); ) {
    int cap = x;
    while (i < weights.size()) {
      if (cap < weights[i]) {
        break;
      } else {
        cap -= weights[i];
      }
      ++i;
    }
    ++days;
  }
  return days;
}

3.搜索的 low 边界是什么? 最小的载重应该应该是所有货物里面的最大值, 这样可以保证每次能装下任意 1 个货物
4.high 边界是什么？应该是所有的货物之和, 也就是 1 天内把所有的货物都带走 

class Solution {
 public:
  int f(vector<int>& weights, int x) {
    int days = 0;
    for (int i = 0; i < weights.size(); ) {
      int cap = x;
      while (i < weights.size()) {
        if (cap < weights[i]) {
          break;
        } else {
          cap -= weights[i];
        }
        ++i;
      }
      ++days;
    }
    return days;
  }
  int shipWithinDays(vector<int>& weights, int days) {
    int low = 1;
    int high = 1;
    for (int& w : weights) {
      low = max(low, w);
      high += w;
    }
    while (low < high) {
      int mid = low + (high - low) / 2;
      int midNum = f(weights, mid);
      if (midNum == days) {
        high = mid;
      } else if (midNum < days) {
        high = mid;
      } else if (midNum > days) {
        low = mid + 1;
      }
    }
    return low;
  }
};

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

分析:
1.理解题意: 第朵花在 bloomDay[i] 天盛开, 必须用相邻的开放 n 朵花才能构成一束花;
2.制作花的天数 x 和做出来的花束数量f(x)是单调的, 所以写一个函数: x 天能做出多少束花 f(x), 该函数设计成返回值为 bool 类型, 表示 x 天是否能做出 f(x) 束花; 因为问的是需要的最少天数, 所以是搜索左侧边界的二分搜索
3.搜索边界, low = bloomDay数组中天数的最小值, high = bloomDay 中天数的最大值
4.m束花且每束需要k朵, 因此至少需要 mk 朵花, 如果bloomDay < m k, 那么一定不能制作完成返回-1 

bool checkPossible(int days, vector<int>& bloomDay, int m, int k) {
  int bouquetsNum = 0;      // 能做成的花束数量
  int curFlowersNum = 0;    // 当前用几朵花, 从左往右线性去计算能当前能做多少束花
  for (int i = 0; i < bloomDay.size() && bouquetsNum < m; ++i) {
    if (bloomDay[i] <= days) {
      ++curFlowersNum;
      if (curFlowersNum == k) {
        ++bouquetsNum;
        curFlowersNum = 0;
      }
    } else {
      curFlowersNum = 0;
    }
  }
  return bouquetsNum >= m;
}

完整答案如下

class Solution {
 public:
  bool checkFeasible(int days, vector<int>& bloomDay, int m, int k) {
    int bouquetsNum = 0;      // 能做成的花束数量
    int curFlowersNum = 0;    // 当前用几朵花, 从左往右线性去计算能当前能做多少束花
    for (int i = 0; i < bloomDay.size() && bouquetsNum < m; ++i) {
      if (bloomDay[i] <= days) {
        ++curFlowersNum;
        if (curFlowersNum == k) {
          ++bouquetsNum;
          curFlowersNum = 0;
        }
      } else {
        curFlowersNum = 0;
      }
    }
    return bouquetsNum >= m;
  }
  int minDays(vector<int>& bloomDay, int m, int k) {
    // 这里写除法可防止溢出
    if (m > bloomDay.size() / k) {
      return -1;
    }
    int low = INT_MAX;
    int high = 1;
    for (int& curDay : bloomDay) {
      low = min(low, curDay);
      high = max(high, curDay);
    }
    while (low < high) {
      int midDays = low + (high - low) / 2;
      if (checkFeasible(midDays, bloomDay, m, k)) {
        high = midDays;
      } else {
        low = midDays + 1;
      }
    }
    return low;
  }
};

1231.分享巧克力

你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。
你打算和 K 名朋友一起分享这块巧克力，所以你需要将切割 K 次才能得到 K+1 块，每一块都由一些 连续 的小块组成。
为了表现出你的慷慨，你将会吃掉 总甜度最小 的一块，并将其余几块分给你的朋友们。请找出一个最佳的切割策略，使得你所分得的巧克力 总甜度最大，并返回这个 最大总甜度。
示例 1：输入：sweetness = [1,2,3,4,5,6,7,8,9], K = 5 输出：6 解释：你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。
示例 2：输入：sweetness = [5,6,7,8,9,1,2,3,4], K = 8 输出：1 解释：只有一种办法可以把巧克力分成 9 块。
示例 3：输入：sweetness = [1,2,2,1,2,2,1,2,2], K = 2 输出：5 解释：你可以把巧克力分成 [1,2,2], [1,2,2], [1,2,2]。

分析:
1.理解题意总共要将巧克力分成K+1大块, 因为自己要的必须是里面最小的, 并且还要这块尽可能大
2.自己获得的总甜度为x, 这时候分得的巧克力块数为f(x); 自己获得的总甜度和分得的巧克力的块数是单调递减的关系; 题目中要找自己分得的巧克力总甜度最大, 所以是搜索右侧边界的二分搜索 

bool checkFeasible(int selfSweetness, vector<int>& sweetness, int k) {
  int totalCnt = 0;
  int curSweetness = 0;
  // 从小块里面逐个分大块巧克力
  for (int& s : sweetness) {
    curSweetness += s;
    // 大块巧克力的甜度超过自己的甜度, 那么算一块巧克力
    if (curSweetness >= selfSweetness) {
      ++totalCnt;
      curSweetness = 0;
    }
  }
  return totalCnt >= k+1;
}

3.搜索下界为low = 0, high = 总甜度的均值 = sumSweeetness / sweeetness.size() 

class Solution {
 public:
  bool checkFeasible(int selfSweetness, vector<int>& sweetness, int k) {
    int totalCnt = 0;
    int curSweetness = 0;
    // 从小块里面逐个分大块巧克力
    for (int& s : sweetness) {
      curSweetness += s;
      // 大块巧克力的甜度超过自己的甜度, 那么算一块巧克力
      if (curSweetness >= selfSweetness) {
        ++totalCnt;
        curSweetness = 0;
      }
    }
    return totalCnt >= k+1;
  }
  int maximizeSweetness(vector<int>& sweetness, int k) {
    int sumSweetness = 0;
    for (int& s : sweetness) {
      sumSweetness += s;
    }
    int low = 1;
    int high = sumSweetness / (k + 1);
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (checkFeasible(mid, sweetness, k)) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return high;
  }
};

贪心/DP+二分查找

1.还有一类常见问题是使用贪心去搜索, 然后配合二分查找达到效率最大化

1802.有界数组中指定下标处的最大值

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：
1.nums.length == n
2.nums[i] 是 正整数 ，其中 0 <= i < n
3.abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
4.nums 中所有元素之和不超过 maxSum
5.nums[index] 的值被 最大化
返回你所构造的数组中的 nums[index] 。
注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。
示例 1：输入：n = 4, index = 2, maxSum = 6 输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。
示例 2：输入：n = 6, index = 1, maxSum = 10 输出：3 比如: [2,3,2,3,2,2], 且还有很多满足题意的

分析:
1.理解题意: 构造一个数组有n个元素, 任意两个相邻元素之间的绝对值之差不超过1, 且数组所有元素和不超过maxSum, 然后让nums[index]这个元素最可能大, 然后返回这个最大的nums[index]
2.对nums[index]在它的可行搜索区间里面贪心找最大的, 同时也就是nums[index]左侧和右侧都要必须都[求和最小]满足maxSum的约束条件, 也就是按照-1的模式两边递减, 直到最后为1
3.对nums[index]搜索最大的满足可能的情况, 搜索的时候二分搜索, 也就是以nums[index]为自变量x的满足条件的最大和maxSum也就是f(x); nums[index]越大, 满足条件的maxSum就越小
4.在计算当前的求和是否满足<=maxSum的时候, 需要尽量大的nums[index], 所以是命中后收缩左侧边界 

long cal(int midValue, int length) {
  // 用左侧的情况分析, 右侧同理
  // 如果midValue左侧的最大值为midValue-1, 如果左侧长度length刚好等于midValue-1, 根据贪心那么就是从1,..,midValue-1做等差数列求和
  // 比如midValue = 4, length = 3, 左边还有3个元素, 所以是1,2,3
  // 如果length < midValue-1, 那么根据贪心, 左侧应该是, small=(midValue-length),...,midValue-1, 等差数列求和为(small+midValue-1)*length/2
  // 比如midValue = 5, length = 3, 左边还有3个元素, 所以是2,3,4
  // 如果length > midValue-1, 那么根据贪心, 左侧应该是自适应补充一些1, 也就是1,..,1,(midValue-length),...,midValue-1, 等差数列求和为(small+midValue-1)*length / 2
  // 比如midValue = 5, length = 8, 左边还有8个元素, 所以是1,1,1,1,1,2,3,4, 需要补充1的个数为length-(midValue-1)
  if (length < midValue - 1) {
    int small = midValue - length;
    // 等差数列求和
    return (long) (midValue - 1 + small) * length / 2;
  } else {
    int needOnes = length - (midValue - 1);
    return (long) midValue * (midValue - 1) / 2 + needOnes;
  }
}
bool checkFeasible(int mid, int n, int index, int maxSum) {
  int leftLength = index;
  int rightLength = n - index - 1;
  return mid + cal(mid, leftLength) + cal(mid, rightLength) <= maxSum;
}

完整解答

class Solution {
 public:
  long cal(int midValue, int length) {
    if (length < midValue - 1) {
      int small = midValue - length;
      // 等差数列求和
      return (long) (midValue - 1 + small) * length / 2;
    } else {
      int needOnes = length - (midValue - 1);
      return (long) midValue * (midValue - 1) / 2 + needOnes;
    }
  }
  bool checkFeasible(int mid, int n, int index, int maxSum) {
    int leftLength = index;
    int rightLength = n - index - 1;
    return mid + cal(mid, leftLength) + cal(mid, rightLength) <= maxSum;
  }
  int maxValue(int n, int index, int maxSum) {
    int low = 1;
    int high = maxSum;
    while (low < high) {
      int mid = low + (high + 1 - low) / 2; // 向上取整
      if (checkFeasible(mid, n, index, maxSum)) {
        low = mid;
      } else {
        high = mid - 1;
      }
    }
    return high;
  }
};
转载请注明来源, from goldandrabbit.github.io

💰

©2018-2024

Built with Hexo and 3-hexo theme

×

Help us with donation