当前位置：首页 > news >正文

双指针算法篇——一快一慢须臾之间解决问题的飘逸与灵动（2）

news 2024/11/6 4:08:21

前言：

上篇我们讲解了双指针算法的含义以及相关题型讲解，本次则趁热打铁，通过进阶题目的分析与讲解，促使我们更深入和灵活的理解运用双指针算法。

一. 盛最多水的容器

题目链接：11. 盛最多水的容器 - 力扣（LeetCode）

题目分析：

1. 该题要求找到一个区间，数组内存储的元素即代表其对应的高度，宽度则为首尾元素下标之差

2. 根据木桶效应，两个板子一高一低，所能容纳水的高度应该为高度较低的那个

3. 因此，我们只需要逐个遍历相乘，求最大值即可

思路讲解：

1. 暴力解法（会超时）

直接逐个遍历所有结果，并逐次比较，选取最大的区间即可。

设两指针 i , j ，分别指向⽔槽板的最左端以及最右端，此时容器的宽度为 j - i 。由于

容器的⾼度由两板中的短板决定，因此可得容积公式： v = (j - i) * min( height[i], height[j])

代码示例如下：

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int ret = 0;// 两层 for 枚举出所有可能出现的情况for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 计算容积，找出最⼤的那⼀个ret = max(ret, min(height[i], height[j]) * (j - i));}}return ret;}
};

2. 对撞指针

由上述分析可知，装水容器的容积由高度和宽度确定。

我们不妨令左边界为left，右边界为right，假设left[height]<right[height]，那么高度就会取左边界的高度，宽度即为right-left。

现在假设固定一个区间进行遍历，分以下几种情况讨论：

1）固定右边界，左边界向右遍历，宽度一定减小，高度的变化不确定，但一定不会大于右区间的高度，因此容积可能增大，也可能减小。

2）固定左区间，右区间向左遍历，宽度一定减小，高度只会变小或不变，因此容积一定减小

由此可见，固定高度较小区间的情况下容积大小的变化是确定的，因此我们只需固定高度较大的区间遍历即可，这样即可省去大量重复的计算比较。

代码实现：

class Solution {
public:int maxArea(vector<int>& height) {int ret=0;//最大容积int left=0,right=height.size()-1;//确定左右区间while(left<right){int v=min(height[left],height[right])*(right-left);ret=max(ret,v);//求最大容积if(height[left]<height[right]){left++;}else{right--;}}return ret;}
};

二. 有效三角形的个数

题目链接：611. 有效三角形的个数 - 力扣（LeetCode）

题目分析：

1. 题目要求找出数组内可以组成三角形的种类个数，需注意，元素的大小可以重复，但是不能是数组内的同一个元素重复组合。

2. 判定方法：两小数之和大于大数，大数减次小数之差大于最小数

思路讲解：

判定方法中谈到了数大小的比较，因此我们可以先选择对数组进行排序

解法一：暴力解放（会超时）

排序后直接3个for循环进行遍历，此时时间复杂度已经来到了恐怖的n的三次方，基本上都会超时。

代码示例如下：

class Solution {
public:int triangleNumber(vector<int>& nums) {// 1. 排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;// 2. 从⼩到⼤枚举所有的三元组for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {// 当最⼩的两个边之和⼤于第三边的时候，统计答案if (nums[i] + nums[j] > nums[k])ret++;} }}return ret;}
};

解法二：双指针算法

在排序之后，我们可以首先固定一个最长边，假设其位置位于i处，则其坐区间[left,right]内的元素全部小于i处的元素，同时分以下几种情况讨论：

注意：此时区间内left处元素最小，right处元素最大！！！

1. nums[left]+nums[right]>nums[i]，说明满足条件，且该区间内所有元素与right组合均可满足条件，此时right--，缩小区间继续判断

2. nums[left]+nums[right]<=nums[i],说明此时和较小，需要left++，寻找更大的元素进行判断

代码实现：

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());//排序int sum=0;//种类个数总和int n=nums.size();//总元素个数for(int i=n-1;i>=2;i--){int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){sum+=right-left;right--;}//区间内均满足,右区间向左遍历if(nums[left]+nums[right]<=nums[i]){left++;}//小于，左区间向右遍历}}return sum;}
};