6226. 摧毁一系列目标
题意：对于数组中每一个数nums[i]，可以摧毁数组中值等于nums[i]+c*space的数（c为非负整数）,求摧毁最大数量时的最小nums[i]
思路：如果两个数x，y可以同时被摧毁，则x%space == y%space，用map统计同一类的数量，遍历数组求得最小值。
点击查看代码
class Solution {
public:
int destroyTargets(vector<int>& nums, int space) {
map<int,int>mp;
for(auto x:nums){
mp[x%space]++;
}
map<int,int>::iterator iter;
int ans = 1e9,res = 0;
for(auto x:nums){
if(mp[x%space]>res) {
res = mp[x%space];
ans = x;
}
else if(mp[x%space] == res && x<ans) ans = x;
}
return ans;
}
};
6227. 下一个更大元素 IV
题意：对于数组中的每一个元素，返回大于它的第二个元素的值，若不能找到，返回为-1。
思路1：利用两个单调栈，一个栈存储已经找到一个大于的元素，一个存储还没有找到大于的数。然后对已存储的与nums[i]比较，得出结果。
点击查看代码
class Solution {
public:
vector<int> secondGreaterElement(vector<int>& nums) {
priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
stack<int>st;
int n = nums.size();
vector<int>ans(n,-1);
for(int i = 0;i<n;i++) {
while(!q.empty() && q.top().first < nums[i]){
ans[q.top().second] = nums[i];
q.pop();
}
while(st.size() && nums[st.top()] < nums[i]){
q.push({nums[st.top()],st.top()});
st.pop();
}
st.push(i);
}
return ans;
}
};
思路2：对-nums[i]当作第一关键字序排序，然后将对应的下标i依次入栈，如果能找到两个大于i的下标，则存在，反之则不存在。
点击查看代码
class Solution {
public:
vector<int> secondGreaterElement(vector<int>& nums) {
int n = nums.size();
typedef pair<int,int> pii;
vector<pii>vec;
vector<int>ans(n);
set<int>tmp;
for(int i=0;i<n;i++){
vec.push_back({-nums[i],i});
}
sort(vec.begin(),vec.end());
for(int i=0;i<n;i++){
auto x = tmp.upper_bound(vec[i].second);
if(x != tmp.end() && next(x) != tmp.end()) ans[vec[i].second] = nums[*next(x)];
else ans[vec[i].second] = -1;
tmp.insert(vec[i].second);
}
return ans;
}
};