<p>You are playing a game that contains multiple characters, and each of the characters has <strong>two</strong> main properties: <strong>attack</strong> and <strong>defense</strong>. You are given a 2D integer array <code>properties</code> where <code>properties[i] = [attack<sub>i</sub>, defense<sub>i</sub>]</code> represents the properties of the <code>i<sup>th</sup></code> character in the game.</p>

<p>A character is said to be <strong>weak</strong> if any other character has <strong>both</strong> attack and defense levels <strong>strictly greater</strong> than this character&#39;s attack and defense levels. More formally, a character <code>i</code> is said to be <strong>weak</strong> if there exists another character <code>j</code> where <code>attack<sub>j</sub> &gt; attack<sub>i</sub></code> and <code>defense<sub>j</sub> &gt; defense<sub>i</sub></code>.</p>

<p>Return <em>the number of <strong>weak</strong> characters</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> properties = [[5,5],[6,3],[3,6]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> No character has strictly greater attack and defense than the other.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> properties = [[2,2],[3,3]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The first character is weak because the second character has a strictly greater attack and defense.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> properties = [[1,5],[10,4],[4,3]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The third character is weak because the second character has a strictly greater attack and defense.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= properties.length &lt;= 10<sup>5</sup></code></li>
	<li><code>properties[i].length == 2</code></li>
	<li><code>1 &lt;= attack<sub>i</sub>, defense<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        maxAttack, minAttack = 0, 0 
        for attack, _ in properties:
            minAttack = min(attack, minAttack)
            maxAttack = max(attack, maxAttack)
# 首先找到最大的attack还有最小的attack值（最小attack值也可以放成0）
# 这是为了建一个maxDefense list，把attack的value变成index，这个list长度就是最大attack值 - 最小attack值；
# 然后loop这个properties（不需要排序）把对应的attack（index）上更新当前index上最大的defense值；例如有多个相同的attack(7,9), (7,11)下对应index 7的位置最大的defense则为11。
# 例如[[7,9],[10,7],[6,9],[10,4],[7,5],[7,10]] 得到maxDefense list为[0, 0, 0, 0, 0, 0, 9, 10, 0, 0, 7, 0]; again，attack值是index，对应的defense为value，然后同样的index下，取相同index（attack）下最大的defense。
        maxDefense = [0 for _ in range(minAttack, maxAttack + 2)]
        for attack, defense in properties:
            maxDefense[attack] = max(defense, maxDefense[attack])

# 然后从后往前loop这个maxDefense list，把对应位置的defense值跟前面的对比，保留最大的；这样就能使当前index的值 更新为这个index到最后尾巴的最大的defense值。
# [10, 10, 10, 10, 10, 10, 10, 10, 7, 7, 7, 0]。
        for i in range(len(maxDefense)-2, -1, -1):
            maxDefense[i] = max(maxDefense[i+1], maxDefense[i])

# 然后只需要重新对比原properties里当前的(attack,defense)值，attack数值+1的index位置，因为这个位置的attack值至少比这个当前的attack值大1，并且我们可以知道，从这个index一直到maxDefense尾巴，也就是index(attack)值都比当前的attack值大;
# 然后如果这个(attack+1)index下maxDefense值也比当前的defense值大的话，表示从这里到maxDefense队尾也会有defense比当前defense高；表示当前的attack跟defense就存在一个碾压它的存在，所以自己算做一个weak character，count+=1.
        count = 0 
        for attack, defense in properties:
            if defense < maxDefense[attack+1]:
                count += 1
        return count
        
1314