使用递归查找堆栈中的最小值

Question

我需要在堆栈中递归地找到最小值，然后 return 最小值... 我尝试迭代解决它并且成功了。

我对递归的尝试：

import java.util.Scanner;

public class Main {

    public static int minimalValue(Stack<Integer> s, int min) {
        if (s.isEmpty())
            return min;
        // Save the previous value.
        int prev = s.pop();

        if (!s.isEmpty() && prev < min)
            min = prev;
        return minimalValue(s, min);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        Stack<Integer> stack = new Stack<Integer>();
        stack.push(99);
        stack.push(64);
        stack.push(73);
        stack.push(54);
        stack.push(100);
        stack.push(82);
        stack.push(55);
        stack.push(300);
        System.out.println(minimalValue(stack, stack.top()));

        in.close();
    }
}

如您所见，方法完成后，堆栈中的每个元素都被删除了。你能给我一个更好的解决方案吗？

Answer 1

可以保留原来的Stack如下：

 public static int minimalValue(Stack<Integer> s) {
    if (s.isEmpty())
        return Integer.MAX_VALUE;
    int last = s.pop();
    int min = Math.min(last, minimalValue(s));
    s.push(last);
    return min;
}

这个递归是通过观察 Stack 中的最小值是 Stack 的顶部和 Stack 的最小值之间的最小值而创建的Stack.

通过在每次递归调用后添加弹出的元素，我确保 Stack returns 最终恢复到其原始状态。

请注意，此解决方案不需要将第二个参数传递给递归方法。

测试：

Stack<Integer> stack = new Stack<Integer>();
stack.push(99);
stack.push(64);
stack.push(73);
stack.push(54);
stack.push(100);
stack.push(82);
stack.push(55);
stack.push(300);
System.out.println(minimalValue(stack));
System.out.println (stack);

输出：

54
[99, 64, 73, 54, 100, 82, 55, 300]

如您所见，最后 Stack 包含其所有元素。

Answer 2

这可能是作弊，但是你可以通过克隆它并在克隆上操作来避免修改原始堆栈。

import java.util.Optional;
import java.util.Stack;

class Scratch {
    public static Optional<Integer> minimalValue(Stack<Integer> s, Optional<Integer> min) {
        if (s.empty()) {
            return min;
        }

        Integer topElement = s.pop();
        Integer newMin = Math.min(topElement, min.orElse(topElement));
        return minimalValue(s, Optional.of(newMin));
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(99);
        stack.push(64);
        stack.push(73);
        stack.push(54);
        stack.push(100);
        stack.push(82);
        stack.push(55);
        stack.push(300);

        Stack<Integer> clone = (Stack) stack.clone();
        Optional<Integer> result = minimalValue(clone, Optional.empty());
        System.out.println(result.orElse(null));
    }
}

使用递归查找堆栈中的最小值

Find the minimal value in stack with recursion

java

recursion

stack

min

data-structures