对于A[i]而言，它不在乎A[i-1]是否比它大。即使比它大，也只是引入了一个local inversion，而不会有额外的global inversion。而要避免牵扯更多的global inversion，唯一的要求就是第i-2个元素及之前的所有元素都要比A[i]小。于是我们可以在遍历元素i的过程中，维护一个curMax，记录的是从第0个元素到第i-2个元素的最大值。只要出现curMax > A[i]即返回false。
775.Global-and-Local-Inversions
Folders and files
| Name | Name | Last commit date | ||
|---|---|---|---|---|
parent directory.. | ||||