2022.1.28
1996. 游戏中弱角色的数量
https://leetcode-cn.com/problems/the-number-of-weak-characters-in-the-game/
你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击和防御。给你一个二维整数数组properties，其中properties[i] = [attack[i], defense[i]]表示游戏中第i个角色的属性。
如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为弱角色。更正式地，如果认为角色i弱于存在的另一个角色j，那么attack[j] > attack[i]且defense[j] > defense[i]。
返回弱角色的数量。
示例 1：
输入：properties = [[5,5],[6,3],[3,6]]
输出：0
解释：不存在攻击和防御都严格高于其他角色的角色。示例 2：
输入：properties = [[2,2],[3,3]]
输出：1
解释：第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。示例 3：
输入：properties = [[1,5],[10,4],[4,3]]
输出：1
解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。提示：
2 <= properties.length <= 105
properties[i].length == 2
1 <= attack[i], defense[i] <= 105 太久没做题了思维完全僵化。
 学到的知识点：单调栈，以及C++中的lambda表达式
 虽然想到了要用排序，但是没有想到把攻击力和防御力按照不同顺序排
 大体的思路是，先把攻击力按照降序排列，然后从前往后遍历防御力，如果找到一个角色的防御力小于之前某个角色的防御力，此时如果所有角色的攻击力都不同，那么当前这个角色的攻击力也一定小于那个防御力比他高的角色，那么他是弱角色，因此在遍历过程中需要维护一个int型变量来存储之前的最大防御力值。
 而实际上需要考虑到会有角色攻击力相同的情况，为了避免把某个攻击力等于其他人而防御力低于那个人的角色视为弱角色，可以将攻击力相同的角色内部按照防御力升序排列，这样一来仍然可以进行上一段中所说的查找。
 更加pro的方法是维护一个单调栈，存储角色的防御力，但是单调栈存在更高的空间复杂度。
 排序+遍历：
class Solution {
public:
int numberOfWeakCharacters(vector<vector<int>>& properties) {
sort(properties.begin(),properties.end(),[](vector<int>& v1,vector<int>& v2){
if(v1[0]>v2[0])return true;
else if(v1[0]==v2[0] && v1[1]<v2[1])return true;
else return false;
});
int numOfWeak=0;
int maxDef=-1;
for(int i=0;i<properties.size();i++){
if(properties[i][1]<maxDef){
numOfWeak++;
}
if(properties[i][1]>maxDef){
maxDef=properties[i][1];
}
}
return numOfWeak;
}
}; 排序+单调栈：
class Solution {
public:
int numberOfWeakCharacters(vector<vector<int>>& properties) {
sort(properties.begin(),properties.end(),[](vector<int>& v1,vector<int>& v2){
if(v1[0]<v2[0])return true;
else if(v1[0]==v2[0] && v1[1]>v2[1])return true;
else return false;
});
stack<int> sta;
int numOfWeak=0;
for(int i=0;i<properties.size();i++){
while(!sta.empty() && sta.top()<properties[i][1]){
sta.pop();
numOfWeak++;
}
sta.push(properties[i][1]);
}
return numOfWeak;
}
}; 在记录一个看到的时间最短的思路，感觉到了智商上的差距。
 思路是维护一个新的vector（数组），以数组的下标作为角色的攻击力，其对应的值作为角色的防御力。