面试算法题：基于给定数组A与栈B构造栈C（C#）

Hey there! Let's break down this interview algorithm problem and work through a solution that fits your requirements of O(N²) time complexity.

First, let's make sure we're on the same page with the problem statement (I'll clarify based on the details you provided):

Given an array A (size N, distinct integers 1~N) and a stack B (size N, distinct integers 1~N):

• For each index i in A, the value A[i] tells us the position (counting from the top of B, where top = position 1) of the element that should be placed at position i (counting from the top of C, top = position 0 or 1—we'll use 1-based for clarity) in stack C.
• Our goal is to construct stack C following these rules, with an O(N²) time algorithm.

Since stacks only let us access the top element, we can't directly grab an element from the middle of B. To get an element that's k positions from the top, we'll need to pop the top k-1 elements, retrieve our target, then push those popped elements back. This is an O(N) operation per element, leading to an overall O(N²) time complexity—perfect for the requirement.

Here's the step-by-step breakdown:

• Start with empty stack C: We'll build C from the bottom up because stack operations are LIFO (last-in, first-out). That means we need to add the element that should be the bottom of C first, then work our way up to the top.
• Iterate over A from last index to first: The last index in A corresponds to the bottom of C, so we start there.
• Retrieve the target element from B:
  1. For each A[i] = k, pop the top k-1 elements from B and store them in a temporary stack.
  2. The top element of B is now our target—pop it and push it to C.
  3. Push all elements from the temporary stack back to B to restore its order (minus the element we just moved to C).
• Finish: Once we've processed all elements, C will be in the correct order.

Here's a straightforward pseudocode version of this algorithm:

function buildStackC(A, B):
    N = length(A)
    C = empty stack
    
    # Build C from bottom to top by iterating A in reverse
    for i from N-1 down to 0:
        k = A[i]  # 1-based position from top of B
        temp_stack = empty stack
        
        # Pop k-1 elements to reach the target
        for j in 1 to k-1:
            temp_stack.push(B.pop())
        
        # Grab the target and add to C
        target_element = B.pop()
        C.push(target_element)
        
        # Restore B's order
        while temp_stack is not empty:
            B.push(temp_stack.pop())
    
    return C

• Time Complexity: For each of the N elements, we perform up to N pop/push operations (in the worst case, we have to pop almost all elements to get to the target). This gives us O(N²) total time, which meets the problem's requirement.
• Space: We use a temporary stack that can hold up to N elements, but if the problem strictly prohibits extra space, we could modify this to use C temporarily (though that adds some complexity). For most interview scenarios, the temp stack is acceptable.
• Correctness: By restoring B after each retrieval, we ensure that future operations can correctly access the remaining elements. Since all elements are distinct, we never run into conflicts when retrieving targets.

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