A bi-search way to solve the problem.


  • 0
    J

    Here is the source code. Maybe it is little complicated than others. However I try my best to label the key process with annotations. Thanks for reading the code and putting out my algorithm's problem. Please forgive me if there are some inappropriate words.

    class Solution {
    public:
        int max(int i1, int i2){
            return i1>i2?i1:i2;
        }
        int maxArea(vector<int>& height) {
            int n = height.size();
    // maxheight refers to the top of the given numbers
            int maxheight = 0;
    // This two array record the largest element from the left/right side to the ith element
    //e.g. left[i] refers to the largest element among height[0,...i]
    //e.g. right[j] refers to the largest element among height[j,...n-1]
            int * left = new int[n];
            int * right = new int[n];
            for(int i = 0; i < n; i++){
                left[i] = right[i] = 0;
            }
    // And it cost O(n) to calculate the left and right array , maxheight
            maxheight = height[0];
            left[0] = height[0];
            right[n-1] = height[n-1];
            for(int i = 1; i < n; i++){
                maxheight = max(maxheight, height[i]);
                left[i] = max(left[i-1], height[i]);
            }
            for(int i = n-2; i >= 0; i--){
                right[i] = max(right[i+1], height[i]);
            }
    //Now, we can, for sure, find the max_water in [0, maxheight * (n-1)]
            int l = 0, v = maxheight * (n-1);
            int ans = 0;
            
            while(l <= v){
                int mid = (l+v)/2;
    //We need to check whether the middle of l and v is satisfied.
                if(check(mid, left, right, height)){
                    ans = mid;
                    l = mid+1;
                }else{
                    v = mid-1;
                }
            }
            return ans;
        }
    //The check the answer.
        bool check(int mid, int * left, int * right, vector<int>& height){
            int n = height.size();
            for(int i = 0; i < n; i++){
                if(height[i] == 0)
                    continue;
    // We can assume that the height[i] is the lower level of the two lines, and we need to guarantee the width to meet the large of water.
                int width;
                if(mid % height[i] == 0){
                    width = mid / height[i];
                }else{
                    width = mid / height[i];
                    width++;
                }
                //int width = ceil((float)mid/(float)height[i]); something wrong!!! Change to the preceding code .
    // Now I check to the left and right, to find if there exists a higher line. If I find, this large(mid) can be satisfied.
                if(i + width < n){
                    if(right[i+width] >= height[i])
                        return true;
                }
                
                if(i - width >= 0){
                    if(left[i-width] >= height[i])
                        return true;
                }
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.