leetcode 11. Container With Most Water-蒲公英云

leetcode 11. Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int heightSize = height.size();
        if (height.empty())
            return 0;
        if (heightSize < 2)
            return 0;
        int index=0;
        for (int i = 0; i < height.size(); i++)
            if (height[i]>height[index])
                index= i;
        if (height[index] == 0)
            return 0;
        int max = 0;
        vector<int>starter(heightSize);
        if (index < height.size() / 2)
        {
            int nxt = 0; int i = 0;
            bool f = false;
            while (!f&&i < heightSize - 1)
            {
                if (height[i] == 0)
                    i++;
                else
                {
                    f = true;
                    i = nxt;
                    nxt = heightSize;
                    if (starter[i] == 0)
                    {
                        for (int j = i + 1; j < heightSize; j++)
                        {
                            if (height[j] <= height[i])
                                starter[j] = 1;
                            else
                            {
                                if (f)
                                {
                                    nxt = j;
                                    f = false;
                                }
                            }
                            int h = height[i] < height[j] ? height[i] : height[j];
                            if (h*(j - i)>max)
                                max = h*(j - i);
                        }
                    }
                }
            }
        }
        else
        {
            int nxt = heightSize - 1; int i = heightSize - 1;
            bool f = false;
            while (!f&&i >= 1)
            {
                if (height[i] == 0)
                    i--;
                else
                {
                    f = true;
                    i = nxt;
                    nxt = 0;
                    if (starter[i] == 0 && height[i] > 0)
                    {
                        for (int j = i - 1; j >= 0; j--)
                        {
                            if (height[j] <= height[i])
                                starter[j] = 1;
                            else
                            {
                                if (f)
                                {
                                    nxt = j;
                                    f = false;
                                }
                            }
                            int h = height[i] < height[j] ? height[i] : height[j];
                            if (h*(i - j)>max)
                                max = h*(i - j);
                        }
                    }
                }
            }
        }
        return max;
    }
};