【算法——双指针】
922. 按奇偶排序数组 II
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
main:
vector<int>nums = { 3,1,2,4 };
int i = 0, j = 1;
int n = nums.size() - 1;
while (j < nums.size() && i < nums.size()) //如果奇偶任一方排好了，另一方自然排好了
{
//判断最后一个元素奇偶
if (nums[n] % 2 != 0) {
swap(nums[j], nums[n]);
j += 2; //来到下一个奇数位置
}
else {
swap(nums[i], nums[n]);
i += 2; //来到下一个偶数位置
}
}
287. 寻找重复数
快慢指针
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
main:
vector<int>nums = {};
int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast) //一开始快指针一次2步，慢指针一次1步
{
fast = nums[nums[fast]];
slow = nums[slow];
}
fast = 0; //二者第一次相遇后，快指针重置为初始位置
while (slow != fast) //快慢都一次一步
{
fast = nums[fast];
slow = nums[slow];
}
//最后返回fast和slow都可以
42. 接雨水
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
思想：每个格子上方的水量进行累加，首先求这个格子左边的最大格子和右边的最大值。
如果左边比右边小，那么左边就是一个兜底，我当前格子装水量就是左减当前格子数。
右比左小同理，右边就是兜底。
总结：
min(left_max, max_right)-nums[i]
特例:当前格子数比左右都大，就直接为0，这时候没有人兜底了
最终式子:max(min(left_max, max_right)-nums[i],0)两侧最大值怎么求？
main
vector<int>nums = { 0,1,0,2,1,0,1,3,2,1,2,1 };
int n = nums.size();
vector<int>lmax(n);
lmax[0] = nums[0];
for (int i = 1; i < n; i++) //左侧最大值不断继承
lmax[i] = max(nums[i], lmax[i - 1]);
vector<int>rmax(n);
rmax[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0 ; i--) //右侧最大值不断继承
rmax[i] = max(nums[i], rmax[i + 1]);
int sum = 0;
for (int i = 1; i < n - 1; i++) //计算
sum += max(min(lmax[i - 1], rmax[i + 1]) - nums[i], 0);
cout << sum;
881. 救生艇
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
main:
vector<int>people = { 3,5,3,4 };
int limit = 3;
int n = people.size();
sort(people.begin(), people.end()); //进行一个排序
int l = 0, r = n - 1; //左右指针
int ans = 0; //计数
while (l <= r)
{
//这个边界处理至关重要，防止l和r指向同一个地方重复计数
int sum = l==r ? people[l]:people[l] + people[r];
//最大和最小的都已经装不下来，所以直接最大的单独一个船
if ( sum > limit)
{
ans++; //装当前遍历的最大的
r--;
}
else if( sum <= limit)
{
ans++; //两人一船
l++;
r--;
}
}
return ans;
变种：两个人一船时，必须体重之和为偶数。就把数组中奇偶分开，单独求最优，然后相加。
475. 供暖器
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
main:
vector<int>houses = { 1,5,7,10,12,15 };
vector<int>heaters = { 3,6,10,13,19 };
//进行一个排序是为了找到最优选择
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
int ans = 0; //ans就是目前最优记录
//i指针代表房屋，j指针代表供暖
//for就是一个一个遍历当前房屋最优择
//然后k就是一个lambda表达式，当然你也可以自己定义一个函数，无所谓的
//k解析：首先j进行边界约束。如果距离当前供暖<下一个供暖我们就停止，直接更新ans，否则下一个供暖检测
//注意ans是公用的，自己看题目要求即可
for (int i = 0, j = 0; i < houses.size(); i++)
{
auto k = [=,&j]{return j == heaters.size() - 1 ||
abs(houses[i] - heaters[j]) < abs(houses[i] - heaters[j + 1]);};
while (!k())
j++;
ans = max(ans, abs(houses[i] - heaters[j]));
}
cout << ans << endl;
41. 缺失的第一个正数
算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili
整体思路就是：我们要实现，i下标索引上面放到数值是i+1，当出现间断的时候，就说明找到了target。
void f(vector<int>&nums, int l, int r);//交换函数
main:
vector<int>nums = { -3,2,1,8,5,4,2,3,5,13 };
int l = 0, r = nums.size();
//l指向0，r指向超出的部分，r属性1：代表“垃圾区域”。2：假设《最好的状态》，也是就[1,r]都有
//l前面的元素肯定都满足我们《i上面是i+1的性质》
while (l < r) //l和r装上时说明[1,r]目标完成了
{
if (nums[l] == l + 1) //代表我们找到了预期，直接下一个
l++;
//不符合的放到垃圾区
//nums[l]<=l,这个都<=l了肯定不符合要求，而且我们l之前的元素都已经符合预期了,
//这个没有意义。
//nums[l]>r,都超出我们的《最好状态了》,比我们期望的目标还要大。
//nums[nums[l]-1]==nums[l]代表重复元素
//然后我们的《最好状态变差，--r》
else if (nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l])
f(nums, l, --r);
//不是垃圾元素，就开始排号
else
f(nums, l, nums[l] - 1);
}
return l+1;