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，is空，pop，推送，top，toString（主要方法）。

提前感谢。

Answer 1

我测试了你的方法。你换了两行。您所需要做的就是在测试之后进行递归调用。

public static void removeMin(Stack<Integer> st) {
    if (st == null || st.isEmpty())
        return;
    int min = st.pop();
    if(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]

Answer 2

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

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

您可能应该更改递归方法以返回最小元素。通过这种方式，你可以与它进行比较：

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;
    }
}

我还没测试过。