如何优化按指定条件堆叠砖块算法的时间复杂度？

问题描述 #

给定N块不同长度的砖块，需要将它们堆叠成数量最少的栈。堆叠规则为：砖块𝑖可放置在砖块𝑗上方当且仅当𝐴𝑖 + 𝑥 ≤ 𝐴𝑗（𝑥为给定整数）。

原实现采用贪心策略，将砖块降序排序后逐个放入第一个符合条件的栈，但最坏时间复杂度为𝑂(𝑁²)，当N达到1e6时效率极低。需要将时间复杂度优化至𝑂(𝑁log𝑁)，同时满足以下约束：

• 1 ≤ 𝑁 ≤ 10^6
• 1 ≤ 𝑥 ≤ 10^9
• 1 ≤ 𝐴𝑖 ≤ 10^9

原Python实现 #

def arrange_bricks(N, x, bricks):
    # Sort the bricks in descending order
    bricks.sort(reverse=True)

    # List to hold stacks
    stacks = []

    for brick in bricks:
        placed = False
        for stack in stacks:
            if brick + x <= stack[-1]:
                stack.append(brick)
                placed = True
                break
        
        if not placed:
            stacks.append([brick])

    print(len(stacks))
    for stack in stacks:
        print(len(stack), ' '.join(map(str, stack)))

N, x = map(int, input().split())
bricks = list(map(int, input().split()))
arrange_bricks(N, x, bricks)

优化方案：贪心+最小堆（优先队列） #

思路 #

1. 排序：仍然将砖块按降序排序，保证每次处理的砖块不大于之前的所有砖块，符合贪心策略的最优性（先放大砖块，再放小砖块，尽可能复用现有栈）。
2. 最小堆维护栈顶：使用最小堆存储每个栈的**栈顶元素（即栈中最小的砖块）**和对应的栈列表。堆顶是当前所有栈中最小的栈顶元素，这样我们可以快速判断是否存在符合条件的栈：
   • 如果堆顶的栈顶元素 ≥ 当前砖块 + x，说明这个栈可以容纳当前砖块（因为栈是降序排列，栈顶是最小元素，栈底的元素更大，肯定满足条件），将砖块放入该栈后，更新堆顶为新的栈顶（当前砖块）。
   • 如果堆顶的栈顶元素 < 当前砖块 + x，说明所有栈的栈顶都小于当前砖块 + x，没有栈可以容纳，需要新建一个栈并将其加入堆。

这种方法的时间复杂度为：排序的𝑂(𝑁log𝑁) + 每个砖块处理的𝑂(log𝐾)（𝐾为栈的数量，最坏为𝑁），总时间复杂度为𝑂(𝑁log𝑁)，完全满足1e6级别的数据规模。

优化后的Python实现 #

import heapq

def arrange_bricks(N, x, bricks):
    # Sort bricks in descending order
    bricks.sort(reverse=True)
    
    # Min-heap stores tuples of (stack_top_value, stack_list)
    heap = []
    
    for brick in bricks:
        if heap:
            # Get the stack with the smallest top element
            top_val, stack = heapq.heappop(heap)
            if top_val >= brick + x:
                # Can place current brick on this stack
                stack.append(brick)
                heapq.heappush(heap, (brick, stack))
            else:
                # Cannot place, push back the original stack and create new stack
                heapq.heappush(heap, (top_val, stack))
                new_stack = [brick]
                heapq.heappush(heap, (brick, new_stack))
        else:
            # No stacks yet, create first stack
            new_stack = [brick]
            heapq.heappush(heap, (brick, new_stack))
    
    # Collect all stacks from the heap
    stacks = [stack for _, stack in heap]
    
    print(len(stacks))
    for stack in stacks:
        print(len(stack), ' '.join(map(str, stack)))

N, x = map(int, input().split())
bricks = list(map(int, input().split()))
arrange_bricks(N, x, bricks)

简化版：仅计算栈数量（无栈内容输出） #

如果不需要输出每个栈的具体元素，只需要栈的数量，可以进一步简化：维护一个升序排列的栈顶列表，使用二分查找快速定位符合条件的栈顶，空间复杂度更低：

import bisect

def min_stack_count(N, x, bricks):
    bricks.sort(reverse=True)
    stack_tops = []
    
    for brick in bricks:
        target = brick + x
        # Find the first stack top >= target
        idx = bisect.bisect_left(stack_tops, target)
        if idx < len(stack_tops):
            # Replace this stack top with current brick
            stack_tops[idx] = brick
        else:
            # Create new stack
            stack_tops.append(brick)
    
    return len(stack_tops)

N, x = map(int, input().split())
bricks = list(map(int, input().split()))
print(min_stack_count(N, x, bricks))

关键技术说明 #

• 贪心算法：通过降序排序保证每次优先处理大砖块，尽可能复用现有栈，从而最小化栈的数量，这是问题的核心最优策略。
• 最小堆/二分查找：将栈顶元素的查找时间从𝑂(𝑁)降至𝑂(log𝑁)，这是优化时间复杂度的关键。最小堆适合需要维护动态有序集合并支持快速弹出/插入的场景，而二分查找适合静态有序集合的快速定位。

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