文章目錄

• 解析
• 思路
• 原理
• 代碼
• • 寫法1
  • 寫法2

解析

p_0:左”指針”
p_1:右”指針”
Area:當前雙”指針”代表面積大小
ret:記錄面積最大值

思路

p_0指向數組頭部
p_1指向數組尾部
Area為當前雙”指針”代表的面積
比較Area與ret大小

若height[p_0]>=height[p_1]
——”指針”p_0+1, ”指針”p_1所代表的面積一定小于Area
——”指針”p_0, ”指針”p_1-1所代表的面積可能大于Area
——要求最大面積, 于是p_1自減1
height[p_0]<height[p_1]
——同理有p_0自加1

原理

如何保證被剔除的p_1/p_0不會與除p_0/p_1外的”指針”形成更大的面積
證明：
若height[p_0]>=height[p_1], 則剔出p_1
”指針”p_0, ”指針”p_1所代表的面積=(p_1-p_0)*height[p_1]
存在i>0, ”指針”p_0+i, 與”指針”p_1形成的面積=(p_1-(p_0+i))*min(height[p_0+i], height[p_1])
比較雙方第一項(p_1-p_0) ,(p_1-(p_0+i)) , 得到前者>后者
比較雙方第二項height[p_1], min(height[p_0+i], height[p_1]) , 得到前者>=后者
于是有
被剔除的p_1不可能與p_0+i形成更大的面積

height[p_0]<height[p_1], 剔出p_0同理

代碼

寫法1

int maxArea(int* height, int heightSize){int p_0=0,p_1=heightSize-1,Area,ret=0;while(p_0!=p_1){if(height[p_0]>=height[p_1]){Area=(p_1-p_0)*height[p_1];p_1--;}else{Area=(p_1-p_0)*height[p_0];p_0++;}if(ret<=Area)ret=Area;}return ret; }

寫法2

int maxArea(int* height, int heightSize){int *p_0=height,*p_1=p_0+(heightSize-1),Area,ret=0;while(p_0!=p_1){if(*p_0>=*p_1){Area=(p_1-p_0)*(*p_1);p_1--;}else{Area=(p_1-p_0)*(*p_0);p_0++;}if(ret<=Area)ret=Area;}return ret; }

總結

以上是生活随笔為你收集整理的Leetcode题库 11.盛水最多的容器(双指针法 C实现)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。