文章目錄

• • 1. 題目信息
  • 2. 解題

1. 題目信息

給定 n 個非負(fù)整數(shù) a1，a2，…，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。
在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。
找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

說明：你不能傾斜容器，且 n 的值至少為 2。

圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。

示例:輸入: [1,8,6,2,5,4,8,3,7] 輸出: 49

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/container-with-most-water
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：
LeetCode 42. 接雨水（雙指針、單調(diào)棧）
LeetCode 84. 柱狀圖中最大的矩形（單調(diào)遞增棧）

• 兩個指針 i, j 分別指向首尾，水的面積 $s=\left(j?i\right)?min(hi,hj)$
• 如果哪邊的 h 小，那邊的指針向中間移動

class Solution { public:int maxArea(vector<int>& height) {int i = 0, j = height.size()-1, s, maxS = 0;while(i < j){if(height[i] > height[j]){s = (j-i)*height[j];--j;}else{s = (j-i)*height[i];++i;}if(s > maxS)maxS = s;}return maxS;} }; class Solution { //2020.4.18 public:int maxArea(vector<int>& height) {int i = 0, j = height.size()-1, area = 0;while(i < j){area = max(area, (j-i)*min(height[i],height[j]));if(height[i] <= height[j])i++;elsej--;}return area;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 11. 盛最多水的容器（双指针）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。