初识算法 · 双指针(2)
发布时间：2025-06-24 17:12:31 作者：北方职教升学中心 阅读量：521
目录。
前言：
盛最多水的容器。
题目分析：
算法原理：
算法编写：
有效三角形的数量。
主题分析
算法原理：
算法编写：
前言：
本文介绍了两个主题，盛最多水的容器和有效三角形的数量，Leetcode的主题链接是：
11. 盛最多水的容器 - 扣除（LeetCode）
611. 有效三角形的数量 - 扣除（LeetCode）
介绍这两个话题，会从两个角度介绍，暴力解法和算法，整个主题的解释分为三个部分，题目分析算法原理解释算法编写的三个部分。
现在就进入正题！
盛最多水的容器。
主题分析
题目：
题目实例：
这个话题的要求是找到最大值，值的求法是下标相减 * 二数中小的数量，所以我们可以无论三七二十一直接暴力�即将提出所有值，自然可以通过两个循环来解决，伪代码：
for(...)。
{。{。
//确定右边的边长。
}。
}。
尽管最终的求值部分是等差数列的求和方法，但不影响，最终时间的复杂度仍然是O(N^2)。
为什么求值是*两数中较小的数？c;相信大家都听说过木桶效应：
也就是说，木桶装水的容量不取决于最长的木板，但是最短的木板，所以求值是最小值。
算法原理：
在算法原理部分，我们已经了解了暴力解决方案，因此，暴力解决方案不再重复c;这里有两个数字，确保下标相减 * 最小的数字是最大值，然后找两个数�我们不妨用双指针解决。
容量大小 = 两数中的较小值 * 下标之差。
我们不妨规定左指针从0开始，右指针来自size - 开始，如果我们从同一方向判断，然后就会有两个变量，下标差可能会增加和减少，小值不确定，会有四种情况，很难控制，如果是我们定向的话，让右指针从右边开始，即数组的最后，右指针向左或左指针向右，都是减少下标差距的过程，所以我们想找到最大值�需要保证的是两个数之间的规则。
谁小谁就移动，而且我们需要记录移动前的容量大小，记录后移动后需要比较容量大小。
谁小谁就移动，而且我们需要记录移动前的容量大小，记录后移动后需要比较容量大小。我们可以选择最大的。算法编写：
class Solution {public: int maxArea(vector<int>& height) { int left = 0, right = height.size() - 1; int ret = 0,ans = 0; while(right > left) { ret = min(height[left],height[right]) * (right - left); ans = max(ret,ans); if(height[left] > height[right]) right--; else left++; } return ans; }};
此时已完美通过。
有效三角形的数量。
有效三角形的数量。
题目分析：
标题：
题目示例：
通过示例，我们可以得出的结论a;我们可以使用来标记不同值相同的元素c;即使组成的三角形是一样的。根据题目要求我们得到的第一个信息是，我们需要判断获得的三个元素是否能形成三角形，然后根据初中理论，三角形的充电条件是：两边之和大于第三边。
当我们判断三角形时，必须写三个条件༟是不是有点麻烦？先不管标题中的另一个提示是数组是非负的整数组，也就是说，不会有非整数和负数我们的返回值是一个可以形成三角形的数字。问题不多这里的分析几乎一样。
算法原理：还是那句话遇事不决先暴力。
这个问题的暴力解决方案很简单，我们只需要三个循环，一个循环可以找到一个边缘：
for(){ for() { for() { ///判断三角形是否成立 } }}。
但时间复杂度也是惊人的高，达到了O(N^3)，一般leetcode这个问题，在最后几个样本中，O(N^3)一般会超时。
因此，我们需要找到另一种方法�然后使用双指针算法，对于双指针，影响两个数，这是三个数字，如何操作？我们不妨借助单调性，如果使用单调性，我们遇到了一组数字我们需要判断是否有三角形，这是不是太麻烦了？然后有单调性比如a + b > c，随着指针向右走，两个小数都大于c，其他数字还能不大于吗？到那个地步，我们可以直接ans = 下标之差，以下必须符合条件。所以c为最大边的所有三角形都找到了，--即可。
算法编写：
class Solution {public: int triangleNumber(vector<int>& nums) { int ans = 0; sort(nums.begin(),nums.end()); for(int i = nums.size() - 1; i >= 2 ;i--) { int left = 0,right = i - 1; while(left < right) { if(nums[left] + nums[right] > nums[i]) ans += (right - left),right--; else left++; } } return ans; }};
此时的时间复杂度为O(N^2)，相对于O(N^3)，这是一个很大的提升。以上是两个算法题目的详细说明。以上是两个算法题目的详细说明。感谢阅读！