Very simple O(n) solution


  • 79
    F

    The idea is : to compute area, we need to take min(height[i],height[j]) as our height. Thus if height[i]<height[j], then the expression min(height[i],height[j]) will always lead to at maximum height[i] for all other j(i being fixed), hence no point checking them. Similarly when height[i]>height[j] then all the other i's can be ignored for that particular j.

    class Solution {
    public:
        int maxArea(vector<int> &height)
        {
            int j=height.size()-1,i=0,mx=0;
            
            while(i<j)
            {
                mx=max(mx,((j-i)*(min(height[i],height[j]))));
                
                if(height[i]<height[j])
                 i++;
                 else if(height[i]>=height[j])
                 j--;
            }
            return mx;
        }
    };

  • 0
    F

    Don't post solution here.


  • 2
    J

    Don't view others' solutions before thinking yourself. :p

    And for those who really understand this solution:

    class Solution {
    public:
        int maxArea(vector<int> &height) {
            if (height.empty()) return 0;
            int result = 0;
            int l = 0;
            int r = height.size() - 1;
            while (l < r) {
                int area = (r - l) * min(height[l], height[r]);
                result = max(result, area);
                if (height[l] < height[r]) {
                    do {
                        l++;
                    } while (l < r && height[l-1] >= height[l]);
                } else {
                    do {
                        r--;
                    } while (r > l && height[r+1] >= height[r]);
                }
            }
            return result;
        }
    };
    

    Thanks to @albja16, my algorithm can be further optimized. Welcome to try, guys!


  • 0
    A

    if we may slant the container, is there any O(n) algorithm?


  • 0
    S

    Great Solution


  • 0
    X

    Brilliant solution.


  • 0
    L

    Yes , only small change in compute area


  • 0
    C

    Very convincing reasoning!


  • 0

    Isn't it the same with franticguy's solution?


  • 0
    A

    Good solution. But I beg to differ a little: as for each inner iteration "do-while", you only need to consider the point value bigger than the border point value h[i], h[j]. e.g: 5,4,2,3,6,7,5,8, at first i=0, j=7, the next value that need computing should be h[4] = 6.


  • 0
    M

    this further optimized seems cost more time..I dont know why


  • 0
    A

    Excellent solution


  • 0

    same here, just using else not else if

        public int MaxArea(int[] height) {
            int left = 0;
            int right = height.Length - 1;
            int maxArea = 0;
            
            while (left < right)
            {
                int area = (right - left) * Math.Min(height[left], height[right]);
                if (area > maxArea) maxArea = area;
                
                if (height[left] > height[right]) right--;
                else left++;
            }
            return maxArea;
        }
    

  • 0
    A

    @franticguy why the calculation formula is maxArea=min(height[i],height[j])|j-i|,not regard as a Trapezoid,and the calculation formulation is maxArea=(height[i]+height[j])|j-i|/2


Log in to reply
 

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