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

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

article 2024/11/6 4:17:04

前言：

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

一. 盛最多水的容器

题目链接：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;
        
    }
};