014枚举之指针尺取——算法备赛

枚举是数据结构与算法中基本的操作，常用于解决序列的区间问题。算法界将"双指针"视为其重要分支，类似地当然还有"三指针"，“四指针”，最常见的还是“双指针”，我认为它们应统称为“指针尺取”。
双指针无疑就是定义两个变量记录内存空间位置（一般为线性数组下标）来进行枚举，常见的枚举策略有“反向扫描”，“同向扫描”。

• 反向扫描，两指针的枚举方向不同，又可分为“两端向中间收缩”，“中间向两边扩散”等。
• 正向扫描，两指针的枚举方向相同，起始位置或速度不同,常见的策略有“定右统左”。

定右统左

定右统左是双指针中的常用策略，即固定右端点，统计左端点，常用于区间统计。

子串简写

问题描述

规定长度大于等于k的字符串可以采用 用数值（中间字符数量）代替中间字符保留首尾字符的简写方法。

如k=4 “abjdjda” 可简写为 “a5a”

给定 k,字符串S，首尾字符c1，c2，问S有多少个首尾字符分别为c1,c2的子串可采用上述简写方法.

原题链接

思路分析

采用双指针(前指针i(初始为k-1)，后指针j(初始为0)) 遍历子串长度为k的首尾字符，当j遍历到首字符为c1时，c1_sum++,c1_sum为一个统计数值，表示长度等于k且首字符为c1的子串个数（长度大于等于k且首字符为c1的左边界个数）。每次统计后，i++，j++，保证了两指针始终相距k。

前项指针i遍历到尾字符为c2时，sum+=cl_sum, 表示i位置为右边界，后面跟有c1_sum个左边界符合条件。

以后前项指针i每次遍历到c2时，子串长度会更长，前面统计的左边界肯定都符合条件，直接加cl_sum即可。

代码

#include <bits/stdc++.h> 
using namespace std;
int K;
long long ans=0,c1_sum=0;
string S;
char c1,c2;
int main(){cin>>K>>S>>c1>>c2;for(int i=K-1,j=0;i<S.size();i++,j++){if(S[j]==c1) c1_sum++;if(S[i]==c2) ans+=c1_sum;}cout<<ans;return 0;
}

每种字符至少取k个

问题描述

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。

原题链接

思路分析

求最少分钟数就是求最少操作数，也就是最少取走的字符数。

由于每次只能取两侧的字符，最后保留的就是一个连续的子串。要使取走的字符数最少，相当于求最后满足条件的最长的子串。

遍历r，寻找满足条件的最小的l。

代码

int takeCharacters(string s, int k) {if(k==0)return 0;int n=s.size();int num[3]={0};for(int i=0;i<n;i++){++num[s[i]-'a'];  //频数统计，全部取走}if(num[0]<k||num[1]<k||num[2]<k) return -1;int l=-1;int maxL=0;  //求r，l的最大距离for(int r=0;r<n;r++){num[s[r]-'a']--;  //放回//求最小的满足条件的l，当r加一时，小于l的左边界肯定不符和条件，所以l不用从0开始重新遍历.//此法相当于两次遍历s，时间复杂度为O(n)while(l<r&&(num[0]<k||num[1]<k||num[2]<k)){l++;  num[s[l]-'a']++;  //取走}maxL=max(maxL,r-l);}return n-maxL;
}

统计定界子数组的数目

问题描述

给你一个整数数组 nums 和两个整数 minK 以及 maxK 。

nums 的定界子数组是满足下述条件的一个子数组：

• 子数组中的 最小值 等于 minK 。
• 子数组中的 最大值 等于 maxK 。

返回定界子数组的数目。

子数组是数组中的一个连续部分。

原题链接

思路分析

首先考虑一个简单的情况，nums 的所有元素都在 [minK,maxK] 范围内。

在这种情况下，问题相当于：

同时包含 minK 和 maxK 的子数组的个数。
核心思路：枚举子数组的右端点i，统计有多少个合法的左端点。

遍历 nums，记录 minK 离 i 最近的位置 minI，以及 maxK 离 i 最近的位置 maxI，当遍历到 nums[i] 时，如果 minK 和 maxK 都遇到过，则左端点在 [0,min(minI,maxI)]范围中的子数组，包含 minK 和 maxK，最小值一定是 minK，最大值一定是 maxK。

以 i 为右端点的合法子数组的个数为：min(minI,maxI)+1

回到原问题，由于子数组不能包含在 [minK,maxK] 范围之外的元素，我们需要额外记录在 [minK,maxK] 范围之外的离 i 最近的位置，记作 i0，则左端点在 [i0+1,min(minI,maxI)] 中的子数组都是合法的。

以 i 为右端点的合法子数组的个数为min(minI,maxI)−i0

代码

long long countSubarrays(vector<int>& nums, int minK, int maxK) {long long ans = 0;int min_i = -1, max_i = -1, i0 = -1;for (int i = 0; i < nums.size(); i++) {int x = nums[i];if (x == minK) {min_i = i; // 最近的 minK 位置}if (x == maxK) {max_i = i; // 最近的 maxK 位置}if (x < minK || x > maxK) {i0 = i; // 子数组不能包含 nums[i0]}ans += max(min(min_i, max_i) - i0, 0);  //若i0大于min(min_i, max_i)，则取不到合法子数组}return ans;
}
作者：灵茶山艾府

最高频元素的频数

问题描述

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

原题链接

思路分析

首先直接一点思考，枚举每个数作为最高频的那个数x，看看通过最多k次操作最多能有多少个数变成x，更新最大频数ans，最后的ans就是答案。因为操作是对选取的数加1，所以只需考虑操作比x小的数，选取的数应该小于x且尽量大，这样便可以尽可能操作更多的数。

对于以上分析，我们可以先对数组按升序排序，从左到右遍历，选取当前枚举数为最高频的数，再从当前数开始向左反向遍历确定操作后的最大频数，最后维护更新的ans就是答案。

代码

int maxFrequency(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int ans=1,n=nums.size();long long sum=0;int j=0;for(int i=1;i<n;i++){int t=k;for(int j=i-1;j>=0;j--){t-=nums[i]-nums[j];if(t>=0) ans=max(ans,i-j+1);else break;}}return ans;}

上述代码两次循环，最大复杂度还是来到了O(n^2)，数据规模大，最后超时了，需要优化.

上述代码中，每次枚举一个nums[i]都向左遍历，其实要计算以当前nums[i]为k的ans值，可以借助前一个计算的结果。

定义j指针为前一个nums[i]往左遍历的截止点，求nums[i+1]对应的j指针时，因为nums[i+1]大于等于nums[i],其对应的j指针不可能更小，只会更大(请读者自行分析)，因此只需在原有的j指针上往右移动即可。算法相当于对数组最多两次遍历，时间复杂度为O(n)。

代码

int maxFrequency(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int ans=1,n=nums.size();long long sum=0;int j=0;for(int i=1;i<n;i++){sum+=(long long)(nums[i]-nums[i-1])*(i-j);while(sum>k){sum-=nums[i]-nums[j];j++;}ans=max(i-j+1,ans);}return ans;}

两端向中间收缩

接雨水

接雨水问题可以称的上指针尺取法中反向扫描的经典例题

问题描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

例图

原题链接

思路分析

定义左右指针l，r，初始l=0，r=height.size()-1;

每次判断height[l]<height[r]则 l++，否则 r++，直到l==r;

1. 当height[l]<height[r]时可以确定 l从左到右遍历过程中子数组[0,l]的最大值lmax<height[r]

此时对于下标l处表示的雨水量是 lmax(子数组[0,l]的最大值)-height[l]。

2. 反之 当height[l]>=height[r]时可以确定 r从 右到左遍历过程中子数组[r,n-1]的最大值rmax<=height[l]

此时对于下标r处表示的雨水量是 rmax(子数组[r,n-1]的最大值)-height[r]。

代码

int trap(vector<int>& height) {int ans=0;int l=0,r=height.size()-1;int lmax=0,rmax=0;while(l<r){lmax=max(height[l],lmax);rmax=max(height[r],rmax);if(height[l]<height[r]){ans+=lmax-height[l];l++;}else{ans+=rmax-height[r];r--;}}return ans;}

中间向两端扩散

包含k下标元素的子数组的最大容量

问题描述

给你一个整数数组 nums **（下标从 0 开始）**和一个整数 k 。

一个子数组 (i, j) 的 容量 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。

请你返回子数组（i，j）(i<=k<=j) 的最大可能 容量 。

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 2 * 10^4
• 0 <= k < nums.length

原题链接

思路分析

由于子数组必须包含nums[k],可以定义两个指针left,right，初始时left=k-1，right=k+1，ans=k;

所有目标子数组中最大的min值为nums[k],最小的min值为数组nums的最小值，

从[1,nums[k]]范围中每次枚举最小值i,初始枚举nums[i],然后依次减1；

向左移动left，直到nums[left]<i或left<0

向右移动right，直到nums[right]<i或ritgh>=n(n为nums数组大小)

此时的子数组[left+1，right-1]是最小值为i的最长目标子数组，记录其容量（right-left-1)*i，用它更新历史最大容量。

当i继续减少，而指针没有移动时，此时（right-left-1)不变，i减少，ans=（right-left-1)*i比上阶段所求更小，所以历史最大容量不会改变。

直到枚举到left<0且ritgh>=n，此时的历史最大容量值即为正确答案。

时间复杂度O(n+C),C为nums中元素的取值范围。

代码

class Solution {
public:int maximumScore(vector<int>& nums, int k) {int n = nums.size();int left = k - 1, right = k + 1;int ans = 0;for (int i = nums[k];; --i) {while (left >= 0 && nums[left] >= i) {--left;}while (right < n && nums[right] >= i) {++right;}ans = max(ans, (right - left - 1) * i);if (left == -1 && right == n) {break;}}return ans;}
};

优化

上述代码效率较低的原因是在 i 比 (left,right) 中的最小值更小，但指针没有移动时，计算出的分数是没有意义的。

指针没有移动的原因是 nums[left] 和 nums[right] 都小于 i。

此时我们应当直接把 i 减小至二者的较大值，而不是每次减少 1，这样就可以保证每一次循环中都至少会移动一次指针，就可以将 C 从时间复杂度中移除，总时间复杂度为O(n)

细节

在减少 i 时，需要注意指针已经超出数组边界的情况。

代码

int maximumScore(vector<int>& nums, int k) {int n = nums.size();int left = k - 1, right = k + 1;int ans = 0;for (int i = nums[k];;) {while (left >= 0 && nums[left] >= i) {--left;}while (right < n && nums[right] >= i) {++right;}ans = max(ans, (right - left - 1) * i);if (left == -1 && right == n) {break;}i = max((left == -1 ? -1 : nums[left]), (right == n ? -1 : nums[right]));}return ans;}

指向不同容器的指针尺取

寻找右区间

问题描述

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。

区间 i 的 右侧区间 是满足 startj >= endi，且 startj 最小 的区间 j。注意 i 可能等于 j 。

返回一个由每个区间 i 对应的 右侧区间 下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

原题链接

代码

vector<int> findRightInterval(vector<vector<int>>& intervals) {vector<pair<int, int>> start;  //将intervals拆分为两个数组vector<pair<int, int>> end;int n = intervals.size();for(int i=0; i<n; i++){start.emplace_back(intervals[i][0], i);end.emplace_back(intervals[i][1], i);}sort(start.begin(), start.end());sort(end.begin(), end.end());vector<int> res(n, -1);auto e_iter = end.begin(), s_iter = start.begin();  //两个指针while(e_iter != end.end()){while(s_iter != start.end() && s_iter->first < e_iter->first){s_iter++;}if(s_iter == start.end()) break;res[e_iter->second] = s_iter->second;e_iter++;}return res;}

多指针

统计好三元组的数目

问题描述

给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。

如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。

• 0 <= i < j < k < arr.length
• |arr[i] - arr[j]| <= a
• |arr[j] - arr[k]| <= b
• |arr[i] - arr[k]| <= c

其中 |x| 表示 x 的绝对值。

返回 好三元组的数量 。

原题链接

代码

int countGoodTriplets(vector<int>& arr, int a, int b, int c) {int n=arr.size(),ans=0;vector<int>ids(n);ranges::iota(ids,0);ranges::sort(ids,{},[&](int i){return arr[i];});for(int j:ids){vector<int>left,right;for(int i:ids){if(i<j&&abs(arr[i]-arr[j])<=a) left.push_back(arr[i]);}for(int k:ids){if(k>j&&abs(arr[k]-arr[j])<=b) right.push_back(arr[k]);}int s1=0,s2=0;for(int value:left){while(s2<right.size()&&right[s2]-value<=c) s2++;while(s1<right.size()&&right[s1]-value<-c) s1++;ans+=s2-s1;}}return ans;
}