题解30 | 重复可以替代的东西总会被消除#点击消除#

#include <iostream>
#include <stack>
#include <string>
using namespace std;

string Duplicates(const string &s) {
   stack<char> str;
   for(char c:s){
        //如果栈空 或者 栈顶元素与要输入的元素不相同 —— 进栈
        if(str.empty() || str.top() != c){
            str.push(c);
        }
        else {
            str.pop();//重复时把里边进过的的吐出来
        }
   }

   string res;
   while (!str.empty()) {
        res = str.top() + res;
        str.pop();
   }

   return res.empty() ? "0" : res;//注意最后看字符串是不是空
}

int main() {
    string s;
    cin >> s;
    cout << Duplicates(s) << std::endl;
    return 0;
}

注：for(char c : s) 是 C++11 引入的一种新的 for 循环语法，也称为范围 for 循环或者 foreach 循环。它的意思是：对于集合（容器） s 中的每个元素，将其赋值给变量 c，然后执行循环体中的语句。

这里假设集合 s 是一个字符序列（字符串），所以每次循环中 c 都会被赋值为序列中的下一个字符。

	std::string s = "Hello, World!";
	for (char c : s) {
		std::cout << c << ' ';
	}
	// 输出：H e l l o ,   W o r l d !

算法基本思想：

- 使用栈来模拟点击消除的过程。

- 遍历字符串中的每个字母，如果当前字母与栈顶字母相同，则将栈顶字母出栈；否则将当前字母入栈。

- 最终栈中剩余的字母即为点击消除后的最终形态。

时间复杂度：

- 遍历字符串需要O(n)的时间复杂度，其中n为字符串的长度。

- 栈的操作（入栈和出栈）的时间复杂度为O(1)。

- 因此，整个算法的时间复杂度为O(n)。

空间复杂度：

- 使用了一个栈来存储字母，栈的最大空间取决于字符串中的相邻相同字母的个数。

- 最坏情况下，字符串中的所有字母都是相邻的相同字母，栈的空间复杂度为O(n)。

- 因此，整个算法的空间复杂度为O(n)。