Container With Most Water

解题思路

惭愧。。。看了解答才写出最终答案。

  1. 最朴素的思路自然是暴搜，时间复杂度 O(n2)

  2. 一直往 DP 去想了，想了半天结论是没法用 DP，没换思路

  3. 数组问题需要注意双指针法。

代码

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

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