[Lc双指针_2] 盛水最多的容器 | 有效三角形的个数 | 和为S的两个数字
目录
🎢1. 盛水最多的容器
题解
代码
🎢2. 有效三角形的个数
题解
代码
3. 和为S的两个数字
解法
前文回顾：[Lc优选算法] 快慢指针 | 移动零 | 复写零 | 快乐数
🎢1. 盛水最多的容器
题目链接：11.盛水最多的容器
题目描述：
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。木桶 效应：
- 两个长度 ，选择最低的才是 木桶盛水高度
8*5=40
7*7=49
示例 2：
输入：height = [1,1]
输出：1提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
题解
解法一：暴力求解(O(N^2)会超时)
枚举出能构成的所有容器，找出其中容积最大的值。
容器容积的计算方式：
- 设两指针 i , j ，分别指向水槽板的最左端以及最右端，此时容器的 宽度为 j - i 。由于容器的⾼度由两板中的短板决定，因此可得 容积公式 ： v = (j - i) * min( height[i], height[j] ）
class Solution {
public:
int maxArea(vector<int>& height) {
int n=height.size(),ret=0,v=0;
//n-1 是要运行的
for(int i=0;i<n;i++)
{
for(int j=1;j<n;j++)
{
v=(j-i)*min(height[i],height[j]);
ret=max(v,ret);
}
}
return ret;
}
};
常见报错 可参考这篇文章：
解法二：暴力优化 双指针(对撞指针)
为了⽅便叙述，假设「左边边界」⼩于「右边边界」
- 发生移动，容器的宽度⼀定变⼩
- 由于左边界较⼩，决定了⽔的⾼度
-
- 如果改变左边界，新的⽔⾯⾼度不确定，因此容器的容积 可能 会增⼤
- 但是对于移动 右边界 的情况
【设置 固定场景，发现这种规律之后，我们就可以来实现优化啦】
- 由此可⻅，左边界和其余边界的组合情况都可以舍去
-
- 所以可以
left++跳过这个边界，继续去判断下⼀个左右边界
- 所以可以
移动 h 较小的部分，它才有机会变大
我们设计的边界情况，就可以利用 单调性
使从边界向内移，w 一定会减小
- 不断重复上述过程，每次都可以舍去⼤量不必要的枚举过程，直到
left与right相遇
-
- 期间产⽣的所有的容积⾥⾯的最⼤值，就是最终答案
代码
设计场景：从边界向内移，w 一定会减小，重点：是去移动 值最小的指针，看它有没有机会变大~
class Solution {
public:
int maxArea(vector<int>& height) {
int ret=0,v=0;
int left=0,right=height.size()-1;
//不相遇 就一直判断
while(left!=right)
{
int h=min(height[left],height[right]);
v=(right-left)*h;
ret=max(ret,v);
if(height[left]>height[right]) right--;
else left++;
}
return ret;
}
};🎢2. 有效三角形的个数
题目链接：633.有效三角形的个数
题目描述：
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3示例 2:
输入: nums = [4,2,3,4]
输出: 4题解
一般三角形我们判断方法是任意两边之和大于第三边
算法原理:
解法一: 暴力求解
- 选三个数进行判断，一般我们一定会想到 三层for循环进行判断，下面是伪代码，时间复杂度O(N^3)
for(int i;i<n-2;i++)
for(int j=i+1;j<n-1;j++)
for(int k=j+1;k<n;k++)
check(i,j,k);关于 for 循环判断的理解：
for(int i;i<n;i++)
//-->
while(!(i<n))
{
int i;
//run
i++;
}
//++到 直到 小于一个数就不要了解法二：利用单调性，使用双指针算法来解决问题
任意两边之和大于第三边，三个数需要判断三次
a+b>c
a+c>b
b+c>a
现在a、b、c三个数，先对它们进行排序，a<=b<=c;
a+b>c
a+c>b
b+c>a
我们只需要判断一次 a+b>c就也把下面两次判断包括了。因为c是最大的！
所以排序实现了对要检查三次的优化
但是我们的循环还是要，嵌套三次，怎么办呢？
通过 移动双指针，我们可以 优化 1 层循环，能快速找到 所有成立情况
if (nums[left] + nums[right] > nums[max])
- 说明[left, right - 1]区间上的所有元素均可以与nums[right]构成⽐nums[max]⼤的⼆元组
- 共有 right - left 种
- 因为，移动左指针，就都是成立的，此时 right位置的元素的所有情况相当于全部考虑完毕，right--，减小第二个元素，进⼊下⼀轮判断
if (nums[left] + nums[right] <= nums[max])
- 说明left位置的元素是不可能与[left + 1, right]位置上的元素构成满⾜条件的⼆元组
- left位置的元素可以舍去
- left++，提升第三个元素，进⼊下一判断
注意这只是固定了10 的一次循环，还要在从后往前固定
- 先 固定 最大的数
- 在最大数的左区间内，使用双指针算法，快速统计符合要求的三元组个数
代码
class Solution {
public:
int triangleNumber(vector<int>& nums)
{
//利用 迭代器排序
sort(nums.begin(),nums.end());
int ret=0;
int n=nums.size();
for(int k=n-1;k>=2;k--)
{
//left和right是每次k都要变化的
int left=0,right=k-1;
while(left<right)
{
if(nums[left]+nums[right]>nums[k])
{
ret+=(right-left);
//中间 剩下的这些，就都是成立的了
right--;//判断下一个 第二个元素
}
else
{
//直到找到 可以搭配第二个元素的 第三个元素
left++;
}
}
}
return ret;
}
};3. 和为S的两个数字
题目链接：JZ57 和为S的两个数字
题目描述：
输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。
数据范围: 0≤len(array)≤105 0≤len(array)≤105 ， 1≤array[i]≤106 1≤array[i]≤106
示例1
输入：[1,2,4,7,11,15],15复制
返回值：[4,11]复制
说明：返回[4,11]或者[11,4]都是可以的 示例2
输入：[1,5,11],10复制
返回值：[]复制
说明：不存在，返回空数组 解法
解法一：暴力枚举求解O(N^2)
拿到题我们马上就会想到暴力求解，两层for循环，以下是伪代码
解法2：使用单调性，使用双指针算法解决问题
本题排好序了，我们直接使用双指针即可，一个指向最左边，一个指向最右边。然后根据条件利用单调性一次排除一批。O(N)
