左右指针向中间相遇

桃扇骨 2023-10-13 19:48 43阅读 0赞

[Leetcode原题：Container With Most Water][Leetcode_Container With Most Water] 以及 [华为OD考题–太阳能板最大面积][OD]，底层完全是相同的。有的题解这样解释为什么可以用双指针：  
初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。  
因为每次移动短板，则最短板可能变大，下一个面积可能增大。  
而如果移动长板，则短板不变或者变小，下一个面积必然变小。  
因此应该移动短板。

解释得不够清楚。如果移动短板到更短板，则此状态的面积不是也必然减小吗？而且这种解法没有遍历所有状态，你怎么证明它一定正确呢。以前题为例来讲：

这类题目的本质是如何正确地**缩减搜索空间**1，缩减时你需要证明被缩减掉的空间是不会有解的。比如此时是1号短板和7号短板，7号较短。如果保留更长的1号，不管2,3,…,6号中谁与7号配对，高度一定小于等于7号，同时宽度缩小，所以面积一定小于现在的1、7配对。所以应该削减`j==7`这一列的搜索空间，对应于双指针解法的代码，就是 `j--`，如下图所示：  
![在这里插入图片描述][a9252999994c4f82be034e4bf73dbe91.png]  
[leetcode.cn的官方题解][leetcode.cn]其实也是一个意思：  
![在这里插入图片描述][80081e7eb2364147921dd813f7fc043b.png]

可用相同方式解的：  
[Leetcode 167. Two Sum II - Input Array Is Sorted][]  
[Leetcode 240. Search a 2D Matrix II][]

--------------------

1.  [O(n) 双指针解法：理解正确性、图解原理（C++/Java）][O_n_ _C_Java] ↩︎

[Leetcode_Container With Most Water]: https://leetcode.com/problems/container-with-most-water
[OD]: https://blog.csdn.net/G1useppE/article/details/124780308
[a9252999994c4f82be034e4bf73dbe91.png]: https://img-blog.csdnimg.cn/a9252999994c4f82be034e4bf73dbe91.png
[leetcode.cn]: https://leetcode.cn/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/
[80081e7eb2364147921dd813f7fc043b.png]: https://img-blog.csdnimg.cn/80081e7eb2364147921dd813f7fc043b.png
[Leetcode 167. Two Sum II - Input Array Is Sorted]: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/submissions/997663838/
[Leetcode 240. Search a 2D Matrix II]: https://leetcode.com/problems/search-a-2d-matrix-ii/submissions/997769612/
[O_n_ _C_Java]: https://leetcode.cn/problems/container-with-most-water/solution/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu/