leetcode 11
思路
問題分析
拆解問題，面積 = 底 * 高
- 寬度：兩個豎直線之間的距離，顯然是 right - left
- 高度：容器的水位受限于較短的那根豎直線的高度，所以高度為 min(height[left], height[right])
本題其實很容易想到暴力解法，通過雙重遍歷，計算每一對豎直線所能形成的容器的面積，并記錄最大面積。但這種方法的時間復雜度是 O(n2)，效率較低，并且無法在leetcode中通過
優化解法-雙指針法
- 由于容器的面積受制于最短的那根豎直線，所以優化的關鍵在于動態調整左右指針的指向，跳過不必要的比較
- 我們使用雙指針的方式，初始化 left 指針在數組的開頭，right 指針在數組的末尾，計算當前容器的面積：
- 如果 height[left] < height[right]，則移動 left 指針，目的是嘗試找到一個更高的左邊豎直線，增加可能的面積。
- 如果 height[left] >= height[right]，則移動 right 指針，嘗試找到一個更高的右邊豎直線。
- 每次移動指針時，都會計算并更新最大面積
為什么雙指針法有效
- 雙指針法通過始終選擇最短的豎直線來決定移動哪一邊指針。因為較短的那根豎直線是面積的瓶頸，只有嘗試替換較短的線，才能可能增加容器的面積
- 如果我們不這么做，選擇較長的線是沒有意義的，因為更短的那條線限制了容器的容量
實現
var maxArea = function (height) {let left = 0, right = height.length - 1;let max = 0;while (left < right) {let min = Math.min(height[left], height[right])const area = (right - left) * min;max = Math.max(max, area)if (min === height[left]) {// 左邊值更小left++} else {right--}}return max;
};
)