解题思路

这是一个栈的递归逆序问题。通过递归遍历和重新赋值来实现栈的逆序操作。

关键点：

  1. 使用双指针记录当前处理的位置
  2. 递归保存原始元素
  3. 回溯时重新赋值实现逆序

算法步骤：

  1. 递归遍历记录原始元素顺序
  2. 在回溯过程中重新赋值
  3. 实现栈的逆序效果

代码

class ReverseStack {
private:
    void reverseHelper(vector<int>& stack, int high, int low) {
        if (high < low) {
            return;
        }
        
        int current = stack[low];
        reverseHelper(stack, high, low + 1);
        stack[high - low] = current;
    }
    
public:
    vector<int> reverseStackRecursively(vector<int>& stack, int top) {
        reverseHelper(stack, top - 1, 0);
        return stack;
    }
};

import java.util.*;
public class ReverseStack {
    private void reverseHelper(int[] stack, int high, int low) {
        if (high < low) {
            return;
        }
        
        int current = stack[low];
        reverseHelper(stack, high, low + 1);
        stack[high - low] = current;
    }
    
    public int[] reverseStackRecursively(int[] stack, int top) {
        reverseHelper(stack, top - 1, 0);
        return stack;
    }
}

class ReverseStack:
    def reverse_helper(self, stack, high, low):
        if high < low:
            return
            
        current = stack[low]
        self.reverse_helper(stack, high, low + 1)
        stack[high - low] = current
        
    def reverseStackRecursively(self, stack, top):
        self.reverse_helper(stack, top - 1, 0)
        return stack

算法及复杂度

  • 算法：递归
  • 时间复杂度：，每个元素只处理一次
  • 空间复杂度：，递归调用栈的深度