Java: 递归查找堆栈中的最小元素

Question

public static void removeMin(Stack<Integer> st)
{
    if (st.isEmpty())
        return;
    int min = st.pop();
    removeMin(st);
    if(min<st.top())
        return;
    st.push(min);
}

我试图找到最小元素并将其删除，但不幸的是我不能。我想得到一些帮助，这是我的代码。

我在Class Stack中只有这些方法：equals、isEmpty、pop、push、top、toString（主要方法）。

提前致谢。

Answer 1

您必须将堆栈顶部的元素与堆栈其余部分的最小元素进行比较。

那不是你在做什么。您只是将堆栈的顶部与堆栈的下一个元素进行比较。

您可能应该将递归方法更改为 return 最小元素。这样你就可以和它比较了：

public static int removeMin(Stack<Integer> st)
{
    if (st.isEmpty())
        return Integer.MAX_VALUE; // if the stack is empty, return a value that is larger 
                                  // than any other value
    int top = st.pop();
    int min = removeMin(st);
    if(top < min) {
        // top is the minimum element
        st.push(min);
        return top;
    } else {
        // min is the minimum element
        st.push(top);
        return min;
    }
}

我还没有测试过。

Answer 2

我测试了你的方法。你有两条线 t运行sposed。您需要做的就是在测试之后放置递归调用。

public static void removeMin(Stack<Integer> st) {
    if (st == null || st.isEmpty())
        return;
    int min = st.pop();
    if(st.isEmpty() || min<st.firstElement())
        return;
    removeMin(st); // this was in the wrong place, causing the stack to empty out completely
    st.push(min);
}

我运行这个例子：

public static void main (String[] args) {
    Stack<Integer> stack = new Stack<>();
    stack.add(2);
    stack.add(1); // to be removed
    stack.add(5);
    stack.add(3);
    stack.add(4);
    removeMin(stack);
    System.out.println(stack.toString());
}

并打印出 [2, 5, 3, 4].

此解决方案适用于位于堆栈顶部、底部或中间任何位置的最小值。

Java: 递归查找堆栈中的最小元素

Java: Recursively Finding the minimum element in a Stack

java

recursion

stack