775. Global and Local Inversions

This is a super fun problem to think. 

Again - let's bring our ultimate tool to start playing with it - DISCRETE THINKING, STEP BY STEP.

1. [3,2] is true - global cnt 1, local cnt 1. Fine
2. [3,2,1] is False - global cnt 3, local 2. What do we get here? To have [a, b, c] to return True, a may be > b, but c has to >= a
3. Given observation at #2, only 2k, and 2k+1 (k in Integer) can be swapped  - picture it in your mind: we can only mess up with 2 consecutive numbers. So the value offset of each # can only be MAX to 1

原文地址:https://www.cnblogs.com/tonix/p/8404918.html