Kotlin函数时间复杂度优化：闸机通行函数超时问题求解

Great question! The main performance bottleneck here is your while loop incrementing currentTime by 1 every iteration—when the maximum time in your input is up to 1e9, this loop will run a billion times, which is way too slow. Let's fix that with some targeted optimizations that cut down unnecessary iterations and handle events in bulk.

Key Issues in the Original Code #

1. 逐秒推进时间: The loop increments currentTime one second at a time, which is catastrophic for large time values.
2. Unordered Queues: Your current queues (inQueue, outQueue) are populated by iterating over input indices, which means they aren't guaranteed to be sorted by arrival time if the input time array is unordered. This could lead to incorrect processing and extra checks.
3. Inefficient Input Validation: Using max() and min() for direction validation requires two full traversals of the array—we can do better with a single pass.

Optimized Solution #

Here's the revised code with explanations of each improvement:

import java.util.PriorityQueue

fun getTimess(time: Array<Int>, direction: Array<Int>): Array<Int> {
    // Input validation (optimized)
    if (time.size != direction.size || time.size > 100_000) return emptyArray()
    if (!direction.all { it in 0..1 }) return emptyArray()
    val maxTime = time.maxOrNull() ?: 0
    if (maxTime > 1_000_000_000 || maxTime < 0) return emptyArray()
    if (maxTime == 0) return Array(time.size) { 0 }

    val result = Array(time.size) { 0 }
    
    // Use PriorityQueues (min-heaps) to keep passengers sorted by arrival time
    val inQueue = PriorityQueue<Pair<Int, Int>>(compareBy { it.first }) // (time, index)
    val outQueue = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })

    for (i in time.indices) {
        if (direction[i] == 1) {
            outQueue.add(time[i] to i)
        } else {
            inQueue.add(time[i] to i)
        }
    }

    var currentTime = 0
    var turnstile = -1 // -1: unused, 0: in, 1: out

    while (inQueue.isNotEmpty() || outQueue.isNotEmpty()) {
        // Jump to the next arrival time instead of incrementing by 1
        val nextInTime = inQueue.peek()?.first ?: Int.MAX_VALUE
        val nextOutTime = outQueue.peek()?.first ?: Int.MAX_VALUE
        val nextEventTime = minOf(nextInTime, nextOutTime)

        if (currentTime < nextEventTime) {
            currentTime = nextEventTime
            turnstile = -1 // Turnstile is unused during the gap
        }

        // Process as many same-direction passengers as possible in one go
        var processed = false
        // First check out direction (matches original logic priority)
        while (outQueue.isNotEmpty() && outQueue.peek().first <= currentTime) {
            if (turnstile == 1 || turnstile == -1 || inQueue.isEmpty() || inQueue.peek().first > currentTime) {
                val (_, idx) = outQueue.poll()
                result[idx] = currentTime
                currentTime++
                turnstile = 1
                processed = true
            } else {
                break
            }
        }
        // If no out passengers processed, check in direction
        if (!processed && inQueue.isNotEmpty() && inQueue.peek().first <= currentTime) {
            val (_, idx) = inQueue.poll()
            result[idx] = currentTime
            currentTime++
            turnstile = 0
        }
    }

    return result
}

What Changed & Why #

1. Priority Queues: We replaced LinkedList with PriorityQueue (min-heaps) to ensure passengers are always processed in arrival time order. This fixes potential bugs if the input time array is unordered and removes the need for extra sorting steps.
2. Jump to Next Event Time: Instead of incrementing currentTime by 1, we calculate the next time a passenger arrives and jump directly to that time. This eliminates millions/billions of unnecessary iterations when there are large gaps between passenger arrivals.
3. Bulk Processing: When the turnstile is set to a direction, we process all eligible passengers for that direction in a single inner loop. This reduces the number of loop iterations by handling multiple passengers at once.
4. Optimized Validation:
   • We first check that time and direction are the same size (a critical validation the original code missed!).
   • direction.all { it in 0..1 } validates directions in a single pass, stopping early if an invalid value is found.
   • maxOrNull() is used instead of max() ?: 0 for safer null handling.

Performance Impact #

With these changes, the time complexity drops from O(T) (where T is the maximum time value) to O(N log N) (dominated by PriorityQueue operations, where N is the number of passengers). This makes the function easily handle the upper limits of input size (100,000 passengers) and maximum time values (1e9) without timing out.

内容的提问来源于stack exchange，提问作者Jerry Okafor