题目描述：给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为(i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：不能倾斜容器，且n的值至少为2

图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]

示例：

输入：[1,8,6,2,5,4,8,3,7]

输出：49

思路过程：

一、暴力法思想

​ 从数组开头或者结尾进行遍历，然后在进行一遍遍历，穷举所有组合，比较出最大的面积区域，算法复杂度：O(n^2)，空间复杂度：O(1)

代码：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxarea = 0;  // 存储找到的最大值
        for (int i = 0; i < height.size() - 1; i++ ) {  // 第一层遍历
            for (int j = i + 1;j < height.size(); j++) {   // 第二层遍历
                int currarea;
                if (height[i] > height[j]) {
                    currarea = height[j] * (j-i);
                } else {
                    currarea = height[i] * (j-i);
                }
                if (currarea > maxarea) {
                    maxarea = currarea;
                }
            }
        }
        return maxarea;
    }
};

二、官方给出的题解——双指针法

将两个指针分别指向数组的头尾，然后将指向的数组项值比较小的指针向比较大的一端移动，在这过程中可以找到最大的面积。

代码：

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

反思

暴力解法不难想到，但是我在做题的时候一直在寻找别的办法，就是想不到官方的解题思路。以后做题可以考虑先用暴力法实现，再寻找优化的解决办法。同时注重数据结构的思想。这一题有点动态规划和决策树得到味道