前言:
上篇我们讲解了双指针算法的含义以及相关题型讲解,本次则趁热打铁,通过进阶题目的分析与讲解,促使我们更深入和灵活的理解运用双指针算法。
相关题目及讲解
一. 盛最多水的容器
题目链接: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;}
};
小结:
本篇内容就到此为止啦!欢迎各位佬前来支持斧正,祝大家生活愉快,万事胜意!!!