【算法——双指针】

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)

两侧最大值怎么求？ 

mainvector<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;