Gemstones - 题解

标签与难度

标签: 栈, 字符串, 贪心算法, 模拟, 数据结构难度: 1200

题目大意喵~

你好呀，指挥官！Gromah 和 LZR 遇到了一个宝石谜题，需要我们帮忙的说！(ฅ'ω'ฅ)

墙上有一串五颜六色的宝石，我们可以进行一种神奇的操作：只要找到 连续三个同种类型 的宝石，就可以把它们“咻”地一下拿走！拿走之后，原来它们左右两边的宝石序列会自动合并起来，形成一串新的序列。

比如说，对于序列 "ATCCCTTG"：

我们发现中间有三个连续的 'C'，就把它们拿走。剩下的 "AT" 和 "TTG" 会合并成 "ATTTG"。
在新序列 "ATTTG" 中，我们又发现了三个连续的 'T'！再次拿走它们，剩下的就是 "AG" 啦。

我们的任务就是，对于给定的初始宝石序列，计算出我们最多能进行多少次这样的消除操作。这个次数就是通关密码哦！

解题思路分析

喵哈哈~ 这个问题看起来就像是经典的“消消乐”游戏呢！每当凑齐三个一样的，它们就“嘭”地一下消失掉。这种问题，我的直觉告诉我，可以用一种非常可爱的数据结构来解决，那就是栈（Stack）！

为什么是栈呢？栈是一种“后进先出”（LIFO）的容器，就像一摞猫咪罐头，我们总是先拿走最上面那个。这和我们的问题非常契合！我们只关心最新形成的、连续的宝石序列。

让我们来一步一步分析喵~

核心思想：贪心策略 当我们从左到右遍历宝石序列时，每遇到一个宝石，我们就看看它能不能和前面的宝石凑成三个。一旦凑齐了，我们就应该 立即消除 它们。这是一种贪心策略。为什么它是最优的呢？因为消除一组宝石（比如三个'C'），可能会让原本不相邻的宝石（比如'C'前面的'B'和'C'后面的'B'）变得相邻，从而创造出新的消除机会（比如凑出三个'B'）。如果我们不立即消除，这个机会就永远不会出现。所以，只要有机会消除，就果断出手，这总是最好的选择，不会让我们错过任何可能性，喵！
用栈来模拟 我们可以用一个栈来存放那些暂时还不能被消除的宝石。但是，如果把每个宝石都一个个放进栈里，判断连续三个会很麻烦。一个更聪明的办法是，我们的栈不存单个宝石，而是存放 连续宝石块 的信息！
具体来说，栈里的每个元素可以是一个 pair（或者一个小小的结构体），记录两件事：{宝石类型, 连续数量}。
现在，让我们拿着宝石串 "ATCCCTTG"，来模拟一下这个过程吧~
- 初始状态: 栈是空的 []，消除次数 count = 0。
1. 遇到第一个宝石 'A'：栈是空的，直接把 {'A', 1} 放进去。
  - 栈: [{'A', 1}]
2. 遇到 'T'：和栈顶的 'A' 不一样，是新的宝石块。把 {'T', 1} 放进去。
  - 栈: [{'A', 1}, {'T', 1}]
3. 遇到 'C'：和栈顶的 'T' 不一样，是新的宝石块。把 {'C', 1} 放进去。
  - 栈: [{'A', 1}, {'T', 1}, {'C', 1}]
4. 又遇到 'C'：和栈顶的 'C' 一样！我们把栈顶的宝石块数量加一。
  - 栈: [{'A', 1}, {'T', 1}, {'C', 2}]
5. 又遇到 'C'：还是和栈顶的 'C' 一样！数量再加一。
  - 栈: [{'A', 1}, {'T', 1}, {'C', 3}]
  - 呀！栈顶的 'C' 数量达到3了！触发消除！我们把栈顶的 {'C', 3} 弹出去，并且把消除次数 count 加一。
  - 消除后，栈: [{'A', 1}, {'T', 1}]，count = 1。
6. 遇到 'T'：现在栈顶是 {'T', 1}，和新来的 'T' 一样！数量加一。
  - 栈: [{'A', 1}, {'T', 2}]
7. 又遇到 'T'：还是 'T'，数量再加一！
  - 栈: [{'A', 1}, {'T', 3}]
  - 喵！又凑够三个了！再次消除！弹出栈顶，count 加一。
  - 消除后，栈: [{'A', 1}]，count = 2。
8. 遇到 'G'：和栈顶的 'A' 不一样，是新的宝石块。把 {'G', 1} 放进去。
  - 栈: [{'A', 1}, {'G', 1}]
遍历结束！最终的消除次数就是 count，也就是 2 次。是不是很清晰呢，的说！这种方法只需要从头到尾扫一遍字符串，非常高效哦！

代码实现

这是我根据上面的思路，精心为你准备的C++代码~ 注释很详细，希望能帮到你呐！

cpp

#include <iostream>
#include <string>
#include <stack>
#include <utility> // for std::pair

// 定义一个别名，让代码更清晰喵~
// GemGroup 表示一个连续的宝石块，包含类型(char)和数量(int)
using GemGroup = std::pair<char, int>;

int main() {
    // 为了更快的输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::string gemstones;
    std::cin >> gemstones;

    // 用一个栈来存储连续的宝石块
    std::stack<GemGroup> gem_stack;
    int elimination_count = 0;

    // 遍历输入的每一个宝石
    for (char current_gem : gemstones) {
        // 如果栈是空的，或者当前宝石和栈顶的宝石类型不同
        // 说明这是一个新的宝石块的开始
        if (gem_stack.empty() || gem_stack.top().first != current_gem) {
            gem_stack.push({current_gem, 1});
        } 
        // 否则，当前宝石和栈顶宝石类型相同
        else {
            // 增加栈顶宝石块的数量
            gem_stack.top().second++;
        }

        // 关键一步：检查栈顶的宝石块数量是否达到了3
        // 注意，这里要先判断栈是否为空，防止对空栈进行top()操作
        if (!gem_stack.empty() && gem_stack.top().second == 3) {
            // 达到3个，消除它们！
            gem_stack.pop();
            elimination_count++;
        }
    }

    std::cout << elimination_count << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 这里的 $N$ 是宝石序列的长度。我们只对整个字符串进行了一次完整的遍历。对于每个宝石，我们最多执行一次入栈（push）和一次出栈（pop）操作。栈的这些基本操作都是常数时间 $O(1)$ 的。所以总的时间复杂度是线性的，也就是 $O(N)$ ，非常快哦！
空间复杂度: $O(N)$ 在最坏的情况下，如果整个宝石序列中没有任何连续三个相同的宝石（比如 "ABABAB..."），那么每个宝石都会形成一个新的宝石块并被压入栈中。这样栈的大小就会和输入字符串的长度成正比。所以，我们需要的额外空间是 $O(N)$ 。

知识点总结

这道题虽然简单，但涉及到的思想很常用呢，值得我们好好掌握！

栈 (Stack): 解决这类具有“消除”和“匹配”性质问题的超级利器！它的“后进先出”特性完美契合了处理最近元素的逻辑。无论是括号匹配，还是像本题这样的消除游戏，栈都是首选的数据结构。
贪心算法 (Greedy Algorithm): 我们采取了“只要能消就立即消”的策略。这种在每一步都做出当前看起来最优的选择，并最终得到全局最优解的思路，就是贪心算法的核心。在本题中，这个策略是正确的。
行程长度编码 (Run-Length Encoding) 的思想: 我们没有把每个宝石都存入栈，而是把 (宝石类型, 数量) 这样的“块”存进去。这其实是一种简单的数据压缩思想，在处理连续重复数据时非常有效，能让逻辑更清晰，代码也更简洁。

希望这篇题解能让你豁然开朗，喵~ 如果还有其他问题，随时可以再来找我哦！(＾• ω •＾)

Gemstones - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​