题面描述:

在这个问题中，我们处理的是老鼠进出一个狭小的老鼠洞，遵循栈的特性。每只老鼠都有一个独特的编号，进洞后可以出洞并再次进入，编号可能重复以表示老鼠重新进洞。输入为一行由空格分隔的数字序列，表示老鼠的进洞顺序。输出则是老鼠的出洞顺序，以空格分隔，遵循后进先出的原则。例如，输入为“1 2 3 2 3 4 5”，则输出为“3 2 5 4 3 2 1”，表示老鼠出洞的顺序。

思路：栈 + 哈希表

1.关键因素:"假定序列最后洞是满的" + 样例分析

我们可以理解为:默认情况下老鼠不出洞。除非序列出现重复时。

2.栈模拟 + 哈希表:

考虑遍历每一个入洞的老鼠编号，并将其加入到栈中模拟为洞里的先进后出。

引入哈希表：因为可能出现重复的老鼠，所以我们用哈希表记录一下某个元素是否在栈中。

假设遍历的这个老鼠在之前出现过了，那就将这个老鼠在栈中后面的都先弹出去，然后再将其弹出。此时就可以将弹出的顺序加入到答案中。

注意每次将老鼠弹出后要将map也做相应的更新。最后将栈中还存有的老鼠依次弹出加入到答案中。

题解概述

在这个问题中，我们需要模拟老鼠进出一个狭小的老鼠洞，遵循栈的后进先出原则。关键在于处理老鼠编号的重复情况，以确保最后的出洞顺序正确。为了实现这一点，我们可以使用栈和哈希表来管理老鼠的状态。

关键因素

1. 满洞的假设：题目说明序列的最后状态是洞满的，这意味着我们只需关注在序列中出现的老鼠编号以及它们的进出顺序。默认情况下，老鼠不出洞，除非在序列中再次出现相同的编号。

2. 重复的处理：当我们遍历进洞的老鼠编号时，如果发现某个编号在栈中已经存在，说明这只老鼠之前已经出过洞，此时我们需要将栈中该老鼠后面的所有老鼠依次弹出，直到将这只老鼠弹出为止。

实现步骤

1. 使用栈模拟洞的状态：

   • 使用一个栈来存储当前在洞中的老鼠编号，确保它们遵循后进先出的顺序。

2. 使用哈希表记录老鼠状态：

   • 使用一个哈希表（或集合）来记录老鼠编号是否已经在栈中。这可以帮助我们快速判断某只老鼠是否已经在洞中。

3. 遍历输入序列：

   • 对于每一个老鼠编号：
     • 如果该编号不在哈希表中，说明它是第一次进洞，将其压入栈并标记为已存在。
     • 如果该编号已经在哈希表中，意味着它曾经出过洞，此时我们需要：
       • 依次弹出栈中的老鼠，直到弹出该老鼠为止，同时将弹出的老鼠编号加入到答案列表中。
       • 弹出后更新哈希表，以反映当前的状态。

4. 处理栈中剩余的老鼠：

   • 在处理完输入序列后，栈中可能还有一些老鼠未出洞。我们需要将这些老鼠依次弹出，并将它们的编号加入到答案列表中。

5. 输出结果：

   • 最后输出答案列表中老鼠的编号，确保顺序正确。

代码

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> arr = new ArrayList<>();
        
        // 读取输入直到文件结束符（EOF）或换行
        while (scanner.hasNextInt()) {
            arr.add(scanner.nextInt());
        }

        Deque<Integer> stack = new ArrayDeque<>(); // 用来模拟栈操作
        Set<Integer> st = new HashSet<>(); // 用来检查元素是否在栈中
        List<Integer> res = new ArrayList<>(); // 用来存储结果

        for (int x : arr) {
            // 如果 x 在集合中，弹出栈顶元素直到栈顶元素等于 x
            if (st.contains(x)) {
                while (stack.peek() != x) {
                    int now = stack.pop();
                    // 从集合中删除元素
                    st.remove(now);
                    // 记录弹出的元素
                    res.add(now);
                }
                res.add(stack.peek());
            } else {
                // 如果 x 不在集合中，直接入栈
                stack.push(x);
                st.add(x);
            }
        }

        // 将栈中的剩余元素依次加入结果（逆序）
        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }

        // 输出结果
        for (int x : res) {
            System.out.print(x + " ");
        }
        System.out.println();

        scanner.close();
    }
}

Python

arr = list(map(int, input().split()))
stack = []
# 用集合来判断元素是否在栈中
st = set()
res = []
for x in arr:
    # 如果x在集合中，那么一直弹出栈顶元素，直到栈顶元素等于x
    if x in st:
        while stack[-1] != x:
            now = stack.pop()
            # 从集合中删除元素
            st.remove(now)
            # 记录弹出的元素
            res.append(now)
        res.append(stack[-1])
    else:
        # 如果x不在集合中，那么直接入栈
        stack.append(x)
        st.add(x)
res += stack[::-1]
print(*res)

C++

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <algorithm>

using namespace std;

int main() {
    vector<int> arr;
    int x;

    // 读取输入直到文件结束符（EOF）或换行
    while (cin >> x) {
        arr.push_back(x);
    }

    stack<int> s; // 用来模拟栈操作
    unordered_set<int> st; // 用来检查元素是否在栈中
    vector<int> res; // 用来存储结果

    for (int x : arr) {
        // 如果 x 在集合中，弹出栈顶元素直到栈顶元素等于 x
        if (st.count(x)) {
            while (s.top() != x) {
                int now = s.top();
                s.pop();
                // 从集合中删除元素
                st.erase(now);
                // 记录弹出的元素
                res.push_back(now);
            }
            res.push_back(s.top());
        } else {
            // 如果 x 不在集合中，直接入栈
            s.push(x);
            st.insert(x);
        }
    }

    // 将栈中的剩余元素依次加入结果（逆序）
    while (!s.empty()) {
        res.push_back(s.top());
        s.pop();
    }

    // 输出结果
    for (int x : res) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

题目内容

现有一个狭小的老鼠洞，每次仅能一只老鼠进或者出(类似于栈的特性)，如果通道里有多只老鼠，那么先进洞的老鼠会比晚进洞的老鼠出来更晚，假如有一窝老鼠来串门,我们给每只老鼠单独编个数字号码，$1、2、3...$

允许老鼠进洞后，又出洞，再次进洞，且若众多老鼠都挤满到洞门口了，则不会再有老鼠进洞，最后出洞的顺序就按洞口到洞底的老鼠编号输出。 假如老鼠进洞的顺序是$1、2、3$，那么可能的出洞顺序是$3、2、1$， 考虑到洞未满的情况下，老鼠进洞后又出洞了，也可能是$1、2、3$等，但不可能是$3、1、2$。

现给定一个进洞序列，序列里数字可能重复，重复表示出洞后再次进洞，假定序列最后洞是满的，序列长度小于$10000$，即老鼠编号范围是$[1,10000]$

请给出老鼠出洞的顺序?

输入描述

输入一行数字数列，每个数字之间用英文空格分隔。如1 2 3

输出描述

3 2 1

样例1

输入

1 2 3 2 3 4 5

输出

3 2 5 4 3 2 1

解释

$123$后又出现$2$，说明$2$号老鼠是之前经出洞了，再重新进洞，$2$号老鼠要出洞，需要$3$号老鼠先出洞，因而最先出洞的是$3$号老鼠，接着是$2$号老鼠。$2$号重新进洞后，接着$3$号又进洞，再是$4$号和$5$号，$5$号后面没其它的说明洞口满了。那么出洞顺序就是 3 2 5 4 3 2 1

样例2

输入

1 1 2 3 4 4 5

输出

1 4 5 4 3 2 1

解释

$1$后面又是$1$，说明$1$号老鼠进洞后又出洞了，接着又进洞，接着是$2、3、4$号老鼠进洞，接着又$4$号老鼠进洞，说明$4$号老鼠也是出洞了再进洞的，$5$号后面没其它的说明洞口满了。那么出洞顺序就是 1 4 5 4 3 2 1