【LeetCode100】--- 5.盛水最多的容器【复习回顾】

题目传送门

方法一：使用双指针

算法思想：
1.双指针算法，从两边依次向中间靠拢
2.计算较小的数（高度）与宽度（两指针作差）的乘积（面积）
3.使用临时变量将当前面积存储 依次遍历更新，直到找到最大的面积

class Solution {public int maxArea(int[] height) {int n = height.length;int left = 0,right = n-1;int max = 0,curMax = 0;while(left < right){if(height[left] < height[right]){curMax = height[left] * (right - left);left++;}else{curMax = height[right] * (right - left);right--;}max = Math.max(max,curMax);}return max;}
}

算法思维导图 

复杂度分析：

时间复杂度：O（n），算法使用双指针从数组两端向中间遍历，每次移动一个指针，直到两指针相遇。整个过程中，每个元素仅被访问一次，因此时间复杂度为线性时间。

空间复杂度：O(1)，只用到了常数个临时变量。