知识点

1. 知识点

   1. 单调队列：

      单调队列实际上就是普通的队列，利用特殊的方法让里面的元素单调。单调队列用来解决，具体指明的滑动窗口问题（注意，不是双指针法的滑动窗口技巧，而是具体滑动窗口）

      单调队列，底层应该有一个基本数据结构支持在头部和尾部插入和删除（队列的特性），因此使用双向链表。单调队列应该有3个api，包括max()，push(E e)，pop(E e)

   2. 二分查找的细节问题

      1. 二分查找的mid，为了防止整型溢出，应该写成mid=small+(large-small)/2;

      2. 二分查找的详解：二分查找有多种

         1. 最基本的二分查找

            • 算法：

                int binarySearch(int[] nums, int target) {
                    int left = 0; 
                    int right = nums.length - 1; // 注意
              
                    while(left <= right) { // 注意
                        int mid = left + (right - left) / 2;
                        if(nums[mid] == target)
                            return mid; 
                        else if (nums[mid] < target)
                            left = mid + 1; // 注意
                        else if (nums[mid] > target)
                            right = mid - 1; // 注意
                    }
                    return -1;
                }

            • 分析：
              1、该算法的搜索区间是[left, right]，因此退出条件为left<=right
              2、该算法有缺陷，即如果有序集合中，target不只有一个，则该算法无法获取全部的target的范围。

         2. 可以获取target左侧边界的二分查找

            • 算法：

                int left_bound(int[] nums, int target) {
                    if (nums.length == 0) return -1;
                    int left = 0;
                    int right = nums.length; // 注意
              
                    while (left < right) { // 注意
                        int mid = left + (right - left) / 2;
                        if (nums[mid] == target) {
                            right = mid;
                        } else if (nums[mid] < target) {
                            left = mid + 1;
                        } else if (nums[mid] > target) {
                            right = mid; // 注意
                        }
                   }
              
                   // 判断left
                   if (left == nums.length) return -1;
                   return nums[left] == target ? left : -1;
                }

            • 分析：
              1、寻找左侧边界的二分查找，搜索区间是[left, right)
              2、因为搜索区间是[left, right)，因此，我们使用left=mid+1和right=mid
              3、因为最终left的可能范围为[0, nums.length]，因此需要做left的判断
              4、因为对于nums[mid] == target这种情况，我们选择继续缩小搜索区间的上界，即不断向左收缩，达到锁定左侧边界的目的，因此该算法可以寻找左侧边界。因为搜索区间是[left, right)，因此right=mid即可。
              5、return语句返回left或right都是一样的，因为while的退出条件一定是left==right。这里return left只是习惯使然

         3. 寻找右侧边界的二分查找：

            • 算法：

                int right_bound(int[] nums, int target) {
                    if (nums.length == 0) return -1;
                    int left = 0, right = nums.length;
              
                    while (left < right) {
                        int mid = left + (right - left) / 2;
                        if (nums[mid] == target) {
                            left = mid + 1; // 注意
                        } else if (nums[mid] < target) {
                            left = mid + 1;
                        } else if (nums[mid] > target) {
                            right = mid;
                        }
                   }
                   if (left == 0) return -1;
                   return nums[left-1] == target ? (left-1) : -1;
                }

            • 分析：
              1、右边界的二分查找，总体和左边界一样。只有部分细节不同。
              2、寻找右边界的二分查找，搜索区间为[left, right)。
              3、当nums[mid] == target时，增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧边界的目的。因为搜索区间是[left, right)，因此left=mid+1
              4、这里有个最重要的点：因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left - 1] 可能是 target，因此return时，返回的是left - 1。退出条件是left==right，因此left和right一样，使用left-1是习惯。

      3. 二分查找的应用场景：

         如果一个应用，可以通过线性暴力穷举方式解决，就可以考虑使用二分查找了。整体伪代码框架如下：

          for (int i = 0; i < n; i++) 
              // isOk方法，用来判断为i时，是否可以解决问题。
              if (isOk(i)) 
                  return 结果;

         同时，如果要求最小值，使用求左边界的二分查找；求最大值，使用求有边界的二分查找。

LeetCode算法

1. LeetCode算法

   1. 239.【滑动窗口最大值】

      解题思路：

      该题可以理解为，窗口不断滑动，因此我们需要动态的计算窗口中的最值。对于动态的题，我们可以得到：在一堆数字中，已知最值为A，如果给这堆数添加一个数B，那么比较一下A和B就可以立即算出新的最值；但如果减少一个数，就不能直接得到最值了，因为如果减少的这个数恰好是A，就需要遍历所有数重新找新的最值

      该题在每次窗口移动时，必定要+1元素和-1元素，因此，我们需要一个特殊的数据结构来辅助，即单调队列。

   2. 875.【爱吃香蕉的珂珂】

      解题思路：

      首先，想到可以通过暴力穷举所有的速度，从1开始到N，穷举到最小的可以吃完的速度。

      速度是线性递增的，搜索就是线性搜素，线性搜素自然可以用二分查找来优化。又因为我们需要最小的速度，因此我们可以用一个搜索左侧边界的二分查找来代替线性搜索。

      每次都判断该speed下，是否能吃完香蕉，只要封装一个函数canEat(int[] piles, int speed, int h)即可。