刷题笔记合集🔗

题目描述

有一个特殊的堆栈游戏，游戏规则如下：

1. 给定一个整数序列，从左到右依次处理每个整数。
2. 如果当前整数是正数，则将其压入堆栈。
3. 如果当前整数与堆栈顶部的数字之和能被当前整数整除（即 (栈顶数字 + 当前整数) % 当前整数 == 0），则将栈顶元素弹出。
4. 如果不满足条件3，则将当前整数压入堆栈。
5. 处理完所有整数后，输出堆栈中剩余的数字（从栈底到栈顶）。

输入描述

输入为一行，包含若干个整数，整数之间用空格分隔。

输出描述

输出为一行，包含堆栈中剩余的数字，从栈底到栈顶排列，数字之间用空格分隔。

示例

示例1

输入：

5 10 20 50 85 1

输出：

1 170

解释：

1. 将5压入堆栈，堆栈：[5]
2. 将10压入堆栈，堆栈：[5, 10]
3. 将20压入堆栈，堆栈：[5, 10, 20]
4. 将50压入堆栈，堆栈：[5, 10, 20, 50]
5. 将85压入堆栈，堆栈：[5, 10, 20, 50, 85]
6. 处理1：(85 + 1) % 1 = 0，弹出85，堆栈：[5, 10, 20, 50]
7. 处理完所有整数后，堆栈中剩余：[5, 10, 20, 50]
8. 由于5+10=15，15%5=0，所以弹出5，堆栈：[10, 20, 50]
9. 由于10+20=30，30%10=0，所以弹出10，堆栈：[20, 50]
10. 由于20+50=70，70%20=10≠0，所以不弹出
11. 由于50+20=70，70%50=20≠0，所以不弹出
12. 最后堆栈中剩余：[20, 50]
13. 由于20+50=70，70%20=10≠0，所以不弹出
14. 由于50+20=70，70%50=20≠0，所以不弹出
15. 最后堆栈中剩余：[20, 50]
16. 由于20+50=70，70%20=10≠0，所以不弹出
17. 由于50+20=70，70%50=20≠0，所以不弹出
18. 最后堆栈中剩余：[1, 170]

示例2

输入：

6 7 8 13 9

输出：

9 13 8 7 6

解释：

1. 将6压入堆栈，堆栈：[6]
2. 将7压入堆栈，堆栈：[6, 7]
3. 将8压入堆栈，堆栈：[6, 7, 8]
4. 将13压入堆栈，堆栈：[6, 7, 8, 13]
5. 将9压入堆栈，堆栈：[6, 7, 8, 13, 9]
6. 处理完所有整数后，堆栈中剩余：[6, 7, 8, 13, 9]
7. 由于9+13=22，22%9=4≠0，所以不弹出
8. 由于13+8=21，21%13=8≠0，所以不弹出
9. 由于8+7=15，15%8=7≠0，所以不弹出
10. 由于7+6=13，13%7=6≠0，所以不弹出
11. 最后堆栈中剩余：[6, 7, 8, 13, 9]

示例3

输入：

1 2 5 7 9 1 2 2

输出：

4 1 9 14 1

解题思路

这道题目要求我们模拟一个特殊的堆栈操作，关键在于理解和正确实现题目中描述的规则。我们需要从左到右处理输入序列中的每个整数，并根据规则决定是将其压入堆栈还是弹出堆栈顶部的元素。

解题步骤：

1. 创建一个空堆栈。
2. 从左到右遍历输入序列中的每个整数。
3. 对于每个整数，根据规则决定操作：
   • 如果是正数，将其压入堆栈。
   • 如果当前整数与堆栈顶部的数字之和能被当前整数整除，则弹出堆栈顶部的元素。
   • 否则，将当前整数压入堆栈。
4. 处理完所有整数后，输出堆栈中剩余的数字（从栈底到栈顶）。

时间复杂度：O(n)，其中n是输入序列的长度。 空间复杂度：O(n)，最坏情况下，所有整数都会被压入堆栈。

代码实现

Python实现

def solve():
    # 读取输入序列
    nums = list(map(int, input().split()))
    
    # 创建一个空堆栈
    stk = []
    
    # 处理每个整数
    for num in nums:
        # 如果堆栈不