#P14081. 【栈2】消消乐
-
ID: 1849
Tried: 992
Accepted: 305
Difficulty: 6
【栈2】消消乐
【栈2】消消乐 - Python 实现
前言
在这道题中，我们需要通过栈来模拟一个消除游戏的过程。游戏规则是：当数组中有连续三个相同的数字时，它们会被消除，并且这个过程会重复进行，直到数组中没有连续三个相同的数字为止。栈（Stack）作为一种后进先出（LIFO）的数据结构，非常适合解决这个问题。每当一个新数字进入时，我们可以通过栈顶检查是否满足消除条件，若满足就弹出栈顶的三个元素。
1. 栈的应用
栈是一种后进先出（LIFO）结构，也就是最新压入栈的元素最先被弹出。在这个题目中，我们利用栈来存储元素，并在每次插入一个新元素后，检查栈顶是否有三个连续相同的元素，如果有则将其消除。
2. Python中的栈实现
Python没有专门的栈类型，我们通常使用列表 list 来模拟栈操作，利用 append() 来压栈，利用 pop() 来弹栈。
在 Python 中，pop() 和 pop(i) 都是列表（list）对象的常用方法，用于移除并返回指定位置的元素。它们的区别在于删除的元素的具体位置。下面是它们的简要讲解和区别：
1. pop()
pop() 默认删除并返回列表中的 最后一个 元素。
语法：
list.pop()
- 默认行为：删除并返回列表的最后一个元素。
- 时间复杂度：
O(1)，因为删除最后一个元素不需要移动其他元素，操作非常快速。
示例：
lst = [1, 2, 3, 4, 5]
last_element = lst.pop() # 删除并返回最后一个元素
print(last_element) # 输出: 5
print(lst) # 输出: [1, 2, 3, 4]
- 输出：
- 返回
5，即列表中的最后一个元素。 - 修改后的列表变为
[1, 2, 3, 4]。
- 返回
2. pop(i)
pop(i) 允许你删除并返回 指定索引位置 i 的元素。如果你指定的索引 i 超出了范围，会引发 IndexError 错误。
语法：
list.pop(i)
- 参数：
i是要删除元素的索引位置。- 如果
i是负数，它表示从列表的末尾开始计数。例如，-1是列表的最后一个元素，-2是倒数第二个元素，依此类推。
- 如果
- 时间复杂度：
O(n)，因为删除指定位置的元素后，后面的元素会向前移动以填补空缺。
示例：
lst = [1, 2, 3, 4, 5]
element = lst.pop(2) # 删除并返回索引为2的元素
print(element) # 输出: 3
print(lst) # 输出: [1, 2, 4, 5]
- 输出：
- 返回
3，即索引为2的元素。 - 修改后的列表变为
[1, 2, 4, 5]。
- 返回
负索引示例：
lst = [1, 2, 3, 4, 5]
element = lst.pop(-2) # 删除并返回倒数第二个元素
print(element) # 输出: 4
print(lst) # 输出: [1, 2, 3, 5]
- 输出：
- 返回
4，即倒数第二个元素。 - 修改后的列表变为
[1, 2, 3, 5]。
- 返回
3. 总结
-
pop()：- 删除并返回列表的 最后一个 元素。
- 适用于快速删除末尾元素，时间复杂度是
O(1)。
-
pop(i)：- 删除并返回指定索引位置
i的元素。 - 适用于删除列表中的任意元素，时间复杂度是
O(n)，因为删除元素后需要移动剩余的元素。
- 删除并返回指定索引位置
4. 使用场景
pop()：通常用于处理栈（后进先出，LIFO）结构，删除并获取最后添加的元素。pop(i)：用于删除列表中间或者指定位置的元素，在一些需要动态修改列表内容的场景中使用，比如删除某个特定的元素。
希望这个讲解能帮你更好地理解 pop() 和 pop(i) 的区别和用法！
思路
-
遍历数组中的每个元素并压栈 我们遍历给定的数组，将每个数字依次压入栈中。每次插入一个数字时，我们需要检查栈顶是否存在连续的三个相同数字。
-
检查栈顶是否有三个连续相同的数字 每次压栈之后，我们检查栈顶的三个元素是否相同。如果相同，则将这三个元素消除，也就是从栈中弹出。
-
重复这个过程直到没有三个连续相同的元素 我们继续遍历数组，将剩下的数字继续压栈，并实时进行消除操作。这个过程会持续进行，直到数组遍历完成。
-
输出最终结果 遍历完成后，栈中剩余的元素就是消除后的结果。由于栈是后进先出的结构，最终输出的顺序需要反转。
步骤
步骤 1：遍历数组中的每个元素，并逐一压入栈中
我们遍历数组中的元素，将它们依次压入栈中。每次插入新元素后，我们需要检查栈顶是否有三个连续相同的元素。
代码：
def eliminate_game(arr):
stack = [] # 创建一个空栈
# 遍历数组中的每个元素
for num in arr:
stack.append(num) # 将当前元素压入栈中
步骤 2：检查栈顶是否有三个连续相同的元素
每次插入一个新元素后，我们检查栈顶是否有三个连续相同的元素。如果有三个相同的元素，我们就将这三个元素弹出栈，表示它们已经被消除。
代码：
# 每次插入新元素后，检查栈顶是否有三个相同的元素
if len(stack) >= 3 and stack[-1] == stack[-2] == stack[-3]:
# 如果有三个相同的元素，弹出这三个元素
stack.pop() # 弹出栈顶元素
stack.pop() # 弹出栈顶元素
stack.pop() # 弹出栈顶元素
步骤 3：继续遍历直到数组结束
继续遍历数组中的元素，依次将它们压入栈中，并检查栈顶是否有三个相同的元素。如果有三个相同的元素，就将它们消除。
步骤 4：构建结果数组并输出
遍历结束后，栈中的元素就是消除后的剩余元素。由于栈是后进先出的结构，输出时需要逆序。
代码：
# 构建结果数组
return stack # 返回栈中剩余的元素
步骤 5：输出结果
最后，我们将栈中的元素输出。如果栈为空，则输出 "[]"。
代码：
def main():
# 输入一行数据
arr = list(map(int, input().split()))
# 调用消除函数
result = eliminate_game(arr)
# 输出结果
if not result:
print("[]") # 如果栈为空，输出空数组
else:
print(" ".join(map(str, result))) # 输出栈中的元素
完整代码
def eliminate_game(arr):
stack = [] # 创建一个空栈
# 遍历数组中的每个元素
for num in arr:
stack.append(num) # 将当前元素压入栈中
# 每次插入新元素后，检查栈顶是否有三个相同的元素
if len(stack) >= 3 and stack[-1] == stack[-2] == stack[-3]:
# 如果有三个相同的元素，弹出这三个元素
stack.pop() # 弹出栈顶元素
stack.pop() # 弹出栈顶元素
stack.pop() # 弹出栈顶元素
# 构建结果数组
return stack # 返回栈中剩余的元素
def main():
# 输入一行数据
arr = list(map(int, input().split()))
# 调用消除函数
result = eliminate_game(arr)
# 输出结果
if not result:
print("[]") # 如果栈为空，输出空数组
else:
print(" ".join(map(str, result))) # 输出栈中的元素
if __name__ == "__main__":
main()
题目描述：
给定一个整数数组 arr，你需要实现一个消除游戏。游戏的规则如下：
- 如果数组中存在三个连续的相同整数，那么这三个整数将被消除。
- 消除后，数组中的元素将向左移动填补空缺，可能会形成新的连续相同的元素。
- 你需要重复这个过程，直到数组中不再存在任何三个连续相同的整数。
请你实现一个函数，返回最终的数组结果。
输入：
- 一行输入，包含一个整数数组
arr，数组元素为a_1, a_2......a_n，其中 1≤n≤1000，−106≤ai≤106。
输出：
- 输出一行，包含最终的数组结果，数组元素用空格分隔。如果最终数组为空，输出
[]。
示例
输入：
1 2 3 3 3 2 1
输出：
1 2 2 1
输入：
1 1 1 2 2 2 3 3 3
输出：
[]
样例1解释
在这个示例中，原始数组为 [1, 2, 3, 3, 3, 2, 1]。根据题目的规则，数组中有三个连续的 3，因此这三个 3 会被消除。经过处理后，剩余的元素是 1、2 和 1。最终，输出的数组结果为 1 2 1，表示最终的数组状态。