47 lines
1.2 KiB
Kotlin
47 lines
1.2 KiB
Kotlin
|
class Solution {
|
||
|
|
private fun min(
|
||
|
|
x: Int,
|
||
|
|
y: Int,
|
||
|
|
): Int = listOf(x, y).min()
|
||
|
|
|
||
|
|
private fun max(
|
||
|
|
x: Int,
|
||
|
|
y: Int,
|
||
|
|
): Int = listOf(x, y).max()
|
||
|
|
|
||
|
|
private data class State(
|
||
|
|
val prevMax: Int,
|
||
|
|
val bitCount: Int,
|
||
|
|
val min: Int,
|
||
|
|
val max: Int,
|
||
|
|
) {
|
||
|
|
val sortable: Boolean
|
||
|
|
get() = min >= prevMax
|
||
|
|
|
||
|
|
private fun getSegmentMaximum(
|
||
|
|
prevMax: Int,
|
||
|
|
min: Int,
|
||
|
|
max: Int,
|
||
|
|
): Int =
|
||
|
|
if (min < prevMax) {
|
||
|
|
Int.MAX_VALUE
|
||
|
|
} else {
|
||
|
|
max
|
||
|
|
}
|
||
|
|
|
||
|
|
fun update(num: Int): State =
|
||
|
|
if (bitCount == num.countOneBits()) {
|
||
|
|
State(prevMax, bitCount, min(min, num), max(max, num))
|
||
|
|
} else {
|
||
|
|
State(getSegmentMaximum(prevMax, min, max), num.countOneBits(), num, num)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
private fun getInitialState(num: Int): State = State(Int.MIN_VALUE, num.countOneBits(), num, num)
|
||
|
|
|
||
|
|
fun canSortArray(nums: IntArray): Boolean =
|
||
|
|
nums.fold(getInitialState(nums[0])) { acc, it ->
|
||
|
|
acc.update(it)
|
||
|
|
}.sortable
|
||
|
|
}
|