题目链接

思路

这道题暴力搜是不可能的，在网上看到使用双指针法解决，说一下思路。使用两个指针，pLeft指向数组头，pRight指向数组尾，谁指向的数小就往内侧走一步，直到相遇。操作很简单，但是正确性值得商讨。
设数组为height，而i,j是其最大的面积所在的左右下标。不妨假设pLeft先到达height[i]，pRight仍然在j的右侧。接下来论证pLeft不会在pRight到达j之前离开。
pLeft何时会离开呢？当height[pLeft]小于height[pRight]时,pLeft会向前走。当这个条件成立时，这个面积要大于我们之前假设的i,j所求得的面积，与假设矛盾，因此pLeft会离开i当且仅当pRight经过j，即最大面积被遍历，因此算法正确。

代码

import kotlin.math.max
import kotlin.math.min
fun maxArea(height: IntArray): Int {
    var pLeft = 0
    var pRight = height.size - 1
    var maxArea = 0
    while (pLeft != pRight) {
        maxArea = max(maxArea, (pRight - pLeft) * min(height[pLeft], height[pRight]))
        if (height[pLeft] < height[pRight])
        pLeft++
            else
        pRight--
    }
    return maxArea
}