stack - 给定一个 push 序列，找到所有可能的 pop 序列

Question

例如推送序列是：1,2,3，所有可能的弹出序列如下：

• 1,2,3
• 1,3,2
• 2,1,3
• 2,3,1
• 3,2,1

我在互联网上找到了一个算法，（Java）代码是：

    public static void getAllPopSeq(List<Integer> pushSeq, int n, Deque<Integer> stack, List<Integer> popSeq, List<List<Integer>> res) {

        if (n == pushSeq.size() && stack.isEmpty()) {
            res.add(popSeq);
            return;
        } else {
            Deque<Integer> aux1 = new LinkedList<>(stack);
            Deque<Integer> aux2 = new LinkedList<>(stack);
            if (n < pushSeq.size()) {
                aux1.push(pushSeq.get(n));
                getAllPopSeq(pushSeq, n + 1, aux1, new ArrayList<>(popSeq), res);
            }
            if (!aux2.isEmpty()) {
                popSeq.add(aux2.pop());
                getAllPopSeq(pushSeq, n, aux2, new ArrayList<>(popSeq), res);
            }
        }
    }

但是我真的很难理解这个算法，如果有人可以为我解释一下，那将非常有帮助。

或者您有其他解决方案，您可以在此处发布。

谢谢！

标签： stackdepth-first-searchbacktracking

Answer 1

我重构了一个更清晰易懂的版本，如果我错了，请纠正我。

import java.util.*;

public class Solution {

    // Time Complexity: O(n) ???
    // Space Complexity: O(result size)
    private List<List<Integer>> getAllPopSeq(List<Integer> pushSeq) {
        // recursive
        List<List<Integer>> res = new ArrayList<>();

        List<Integer> seq = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        dfs(pushSeq, 0, stack, seq, res);
        return res;
    }

    private void dfs(List<Integer> pushSeq, int index, Deque<Integer> stack, List<Integer> seq,
                     List<List<Integer>> res) {
        // if current index reach the end of the push seq && stack is empty
        if (index == pushSeq.size() && stack.isEmpty()) {
            // add this sequence into the result list
            res.add(seq);
            return;
        }
        // now we have 2 choices:
        // 1. push the current element into the stack
        // 2. pop the top element in the stack
        // we need to consider all possible sequences
        // push
        if (index < pushSeq.size()) {
            Deque<Integer> stack1 = new ArrayDeque<>(stack);
            stack1.push(pushSeq.get(index));
            dfs(pushSeq, index + 1, stack1, new ArrayList<>(seq), res);
        }
        // pop
        if (!stack.isEmpty()) {
            Deque<Integer> stack2 = new ArrayDeque<>(stack);
            seq.add(stack2.pop());
            dfs(pushSeq, index, stack2, new ArrayList<>(seq), res);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        List<Integer> pushSeq = Arrays.asList(1, 2, 3);
        List<List<Integer>> allPopSeq = s.getAllPopSeq(pushSeq);
        System.out.println(allPopSeq);
    }
}