/*
题目：盛最多水的容器 middle
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
输入：[1,8,6,2,5,4,8,3,7]
输出：49
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。
在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
思路：O(n),暴力是O(n^2)
算法流程： 设置双指针 i,j 分别位于容器壁两端，根据规则移动指针（后续说明），
并且更新面积最大值 maxS，直到 i == j 时返回 maxS。
指针移动规则与证明：
每次选定围成水槽两板高度 h[i],h[j] 中的短板，向中间收窄 1 格。
设每一状态下水槽面积为 S(i,j),(0 <= i < j < n)，由于水槽的实际高度由两板中的短板决定，
则可得面积公式 S(i,j)=min(h[i],h[j])×(j?i)。
在每一个状态下，无论长板或短板收窄 1 格，都会导致水槽底边宽度 ?1：
1）若向内移动短板，水槽的短板 min(h[i],h[j]) 可能变大,可能变小或者不变，因此水槽面积 S(i,j)可能增大。
2）若向内移动长板，水槽的短板 min(h[i],h[j])不变或变小，下个水槽的面积一定小于当前水槽面积。
因此，向内收窄短板可以获取面积最大值，向内收窄长板一档不能获取面积最大值。
*/
package leetCode.Other;public class lc_other_11_maxArea {public int maxArea(int[] height) {int p1 = 0;int p2 = height.length - 1;int s = 0;int maxS = 0;while (p1 != p2) {if (height[p1] >= height[p2]) {s = (p2 - p1) * height[p2];p2--;} else {s = (p2 - p1) * height[p1];p1++;}maxS = Math.max(maxS, s);}return maxS;}}