5.3 how to apply binary search algorithm
5.3.1 problem analysis
- When binary search is applied to practical algorithm problems, it usually has a feature that the search space is ordered.
Ke Ke likes bananas. There are n piles of bananas, and there are piles[i] bananas in pile I. The guards have left and will be back in h hours.
Ke Ke can determine the speed K (unit: root / hour) at which she eats bananas. Every hour, she will choose a bunch of bananas and eat K of them. If the pile of bananas is less than k, she will eat all the bananas in the pile, and then she will not eat more bananas in this hour.
Ke Ke likes to eat slowly, but still wants to eat all the bananas before the guards come back.
Returns the minimum speed K at which she can eat all bananas in h hours (k is an integer).
Source: LeetCode
Link: https://leetcode.cn/problems/koko-eating-bananas
The copyright belongs to Lingkou network. For commercial reproduction, please contact the official authorization. For non-commercial reproduction, please indicate the source.
- That is to say, input a positive integer array of length N, where piles represents n piles of bananas, and piles[i] the number of bananas in the ith pile. Now koko needs to eat these bananas within H hours
- Koko eats bananas at a rate of k per hour, and he can eat a bunch of bananas at most every hour. If he can't eat them, he can save them for the next hour. If he has an appetite after eating them, he will only wait until the next hour to eat them
- Under this condition, please write an algorithm to calculate that Koko needs to eat at least a few bananas per hour to eat them in H hours?
- The algorithm requires the minimum rate of eating bananas within H hours. It is advisable to set Koko's rate of eating bananas as speed. What is the maximum possible speed? At least how much is possible?
At least: it will be at least 1, because it is impossible to eat bananas if it is 0
At most: max(piles) at most, because you can only eat a bunch of bananas at most in an hour
5.3.2 code implementation
- Violent solution: enumerate from 1 to max(piles). Once a certain value is found, all bananas can be eaten within H hours. This is the minimum speed
public int minEatingSpeed(int[] piles, int h) { int max = piles[getMaxIndex(piles)]; int speed; for(speed = 1;speed<=max;speed++){ if(canFinish(piles,speed,h)){ break; } } return speed; }
- Observe this for loop, which is characterized by linear search in continuous space, which is the sign that binary search can play a role. Since the minimum speed is required, a binary search for the left boundary can be used instead of linear search
public int minEatingSpeed(int[] piles, int h) { int left =1,right=piles[getMaxIndex(piles)]+1;//Define the search interval [left, right], right unreachable while (left < right){ int mid = left + (right-left)/2; if(canFinish(piles,mid,h)){ right = mid; }else{ left = mid+1; } } return left; }
- Let's review why we can search for the left boundary in this way
- First, our search interval is [left, right], and then when we want to find the left boundary, the processing is as follows: when we find a reasonable target, we will approach right to the left and keep shrinking to the left, so as to obtain the effect of locking the left boundary
public int minEatingSpeed(int[] piles, int h) { int left =1,right=piles[getMaxIndex(piles)]+1;//Define the search interval [left, right], right unreachable while (left < right){ int mid = left + (right-left)/2; if(canFinish(piles,mid,h)){ right = mid; }else{ left = mid+1; } } return left; } //O(N) private boolean canFinish(int[] piles,int speed,int h){ int time = 0; for (int pile : piles) { time += timeOf(pile,speed); if(time>h){ return false; } } return time<=h; } //How long will it take to eat bananas at speed? private int timeOf(int n,int speed){ //If n > speed, the integer is rounded up. For example, my n is 5 and speed is 2. It takes 3 hours //If n < speed, it only takes one hour return (n/speed)+((n%speed>0)?1:0); } private int getMaxIndex(int[] piles){ int idx=0,max=Integer.MIN_VALUE; for(int i = 0;i<piles.length;i++){ if(max<piles[i]){ max = piles[i]; idx = i; } } return idx; }
5.3.3 extension
Packages on the conveyor belt must be transported from one port to another within days.
The weight of the ith package on the conveyor belt is weights[i]. Every day, we load packages onto the conveyor belt in the order of given weights. We will not load more than the maximum carrying capacity of the ship.
Return the minimum carrying capacity of the ship that can deliver all packages on the conveyor belt within days.
Source: LeetCode
Link: https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days
The copyright belongs to Lingkou network. For commercial reproduction, please contact the official authorization. For non-commercial reproduction, please indicate the source.
- This question is similar to the previous one. Give you a positive integer array weights and a positive integer D, where weights represents a series of goods, and the value of weights[i] represents the weight of the i-th article. The goods are inseparable and must be installed and transported in sequence. Please calculate the minimum carrying capacity of the cargo ship that can carry all the goods in D days
- Our question is the same as the previous one. Let's analyze it first. What is the maximum carrying weight? At least how much?
At least: max(weights), because once it is less than this value, it is impossible to complete the shipment
At most: sum(weights), which can be shipped in one day
- The minimum load is required, so the linear search can be optimized by the dichotomous search algorithm that searches the left boundary
public int shipWithinDays(int[] weights, int days) { int[] maxAndSum = getMaxAndSum(weights); int left = maxAndSum[0],right = maxAndSum[1]+1; //Define the search interval [left, right], right unreachable while (left<right){ int mid = left + (right-left)/2; if(canFinish(weights,days,mid)){ right = mid; }else{ left = mid+1; } } return left; } private int[] getMaxAndSum(int[] weights){ int max = Integer.MIN_VALUE; int sum = 0; for (int weight : weights) { max = Math.max(max,weight); sum += weight; } int[] ans = new int[2];ans[0] = max;ans[1]=sum; return ans; } //If the load is cap, can the goods be transported within D days private boolean canFinish(int[] weights,int days,int cap){ int i = 0; for(int day = 0 ;day<days;day++){ //Initialization load int maxCap = cap;//Indicates the carrying capacity of the day, and then starts loading while ((maxCap -= weights[i]) >= 0){//Keep loading. Once it is less than, it means that the carrying capacity of the day has reached the limit and cannot be loaded again i++; if(i == weights.length){ return true; } } } return false; }
5.4 how to solve the problem of receiving rainwater efficiently
5.4.1 problem description
Given n non negative integers to represent the height map of each column with a width of 1, calculate how much rain can be received by the columns arranged according to this.
[external link image transfer failed. The source station may have anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-foli2yst-1661782052076) (. / image / JYS. PNG)]
- Input a nums array with a length of n to represent a row of columns with a width of 1 in the two-dimensional plane. Each element nums[i] is a non negative frame number and represents the height of the ith column. Now, please calculate how much rain these columns can hold if it rains?
5.4.2 core ideas
- When we find that this problem is completely out of our mind, it is usually because we look at the problem from the perspective of the whole, resulting in the complexity of the problem being amplified. At this time, we may as well consider only the part and start with the part, just like handling strings, not how to handle the whole string, but how to handle each character
- We thought it was difficult before because we saw the whole array. Now we start from a single element and analyze it with i=4 of the title. How much water can be filled when i=4? It's easy to find it at this time. It can hold two pieces of water
- How did you get these two waters? Looking from i=4 to the left, the height of the highest column on the left is 2, looking to the right, the height of the highest column on the right is 3, and the smaller one is taken as the limit. Then the corresponding column height of i=4 is 0, so 2-0 is two water
The above process is represented by code
water[i] = Math.min( //The highest pillar on the left Math.max(height[0...i]) //The highest pillar on the right Math.max(height[i...n-1]) ) - height[i]
- Violent algorithm
public int trap(int[] height) { int n = height.length; int ans = 0; for(int i = 1;i<n-1;i++){ int lMax = 0,rMax = 0; //Look for the highest pillar on the right for(int j = i;j<n;j++){ rMax = Math.max(rMax,height[j]); } //Look for the highest pillar on the left for(int j = i;j>=0;j--){ lMax = Math.max(lMax,height[j]); } //Calculate the water that can be filled ans += Math.min(lMax,rMax) - height[i]; } return ans; }
5.4.3 memo optimization
-
In the previous solution, the maximum value between height[0...i] is calculated every time, and it is solved by loop traversal. But if we know height[0...i-1], will we be able to know height[0...i] by comparing it with height[i]
-
Idea: create two arrays rMax and lMax as memos, where the definition is: lMax[i] represents the height of the highest column in height[0...i], rMax[i] represents the height of the highest column in height[i...n-1]. Note that base case, lMax [0] = height [0], rMax [n-1] = height [n-1]
public int trap(int[] height) { if(height.length == 0){ return 0; } int n = height.length; int ans = 0; int[] lMax = new int[n];lMax[0] = height[0]; int[] rMax = new int[n];rMax[n-1] = height[n-1]; //Calculate lMax from left to right for(int i =1;i<n;i++){ lMax[i] = Math.max(height[i],lMax[i-1]); } //Calculate rMax from right to left for(int j = n-2;j>=0;j--){ rMax[j] = Math.max(height[j],rMax[j+1]); } //Calculate the answer for(int i =1;i<n-1;i++){ ans += Math.min(lMax[i],rMax[i])-height[i]; } return ans; }
5.4.4 double pointer solution
- The idea of this solution is completely consistent with the previous one, but the implementation method is very ingenious. The main difference is that the memo is pre processed in advance, while the double pointer is calculated while walking, which saves space complexity
Core code
public int trap(int[] height) { if(height.length == 0){ return 0; } int n = height.length; int ans = 0; int left = 0; int right =n-1; int lMax = height[0];//lMax is the height of the highest column in height[0...left] int rMax=height[n-1];//rMax is the height of the highest column of height[right...n-1] while (left<=right){ lMax = Math.max(lMax,height[left]); rMax = Math.max(rMax,height[right]); //ans += Math.min(lMax,rMax)-height[i] if(lMax < rMax){ ans += lMax- height[left]; left++; }else{ ans += rMax - height[right]; right--; } } return ans; }
- Solution analysis
Reviewing the previous memo solution, lMax[i] and rMax[i] represent the height of the highest column of height[0...i] and height[i...n-1]
In this double pointer solution, lMax and rMax represent the height of the highest column of height[0...left] and height[right...n-1]
At this time, lMax must be the column with the highest coordinate of the left pointer, but rMax is not necessarily the highest column on the right of the left pointer (according to the definition)
We only care about min(lMax,rMax). Let's think about what kind of situation can ensure that the water we get is right
We know that for the left pointer, the lMax on the left must be the highest column on the left of height[left]. If we want to determine the storage of this grid of water, we must know the highest height of the corresponding column on the right. At this time, there are two cases
[1] At this time, the highest height of the column corresponding to the right generated by the traversal is higher than the highest height on the left. At this time, it can be determined that only Lmax height [left] can be installed
Height of high column
At this time, lMax must be the column with the highest coordinate of the left pointer, but rMax is not necessarily the highest column on the right of the left pointer (according to the definition)
We only care about min(lMax,rMax). Let's think about what kind of situation can ensure that the water we get is right
We know that for the left pointer, the lMax on the left must be the highest column on the left of height[left]. If we want to determine the storage of this grid of water, we must know the highest height of the corresponding column on the right. At this time, there are two cases
[1] At this time, the highest height of the column corresponding to the right generated by the traversal is higher than the highest height on the left. At this time, it can be determined that only Lmax height [left] can be installed
[2] At this time, the highest height of the column corresponding to the right side generated by the traversal is lower than the highest height of the left side. At this time, it can be determined that the main restriction factor of the water contained in the right pointer is the right side. Therefore, at this time, it can be determined that height[right]