1.刪除字符串中所有相鄰的重復字符

注意，我們需要重復處理，而不是處理一次相鄰的相同元素就結束了。對示例來說，如果只進行一次處理，結果為aaca，但是處理之后又出現了相鄰的重復元素，我們還得繼續處理，最后結果就是ca。

解法：借助棧來模擬

? ? ? ? 我們可以將字符串中的元素依次入棧，元素入棧前判斷是否與棧頂元素相等，如果相等就彈出棧頂元素，繼續判斷下一個元素。等到字符串全部入棧，棧中的就是最終答案。

但是我們沒有必要弄一個stack出來，因為這樣最終結果是逆序的，我們可以采用string來模擬棧的行為。?

時間復雜度：O(n)

空間復雜度：O(n)?

class Solution 
{
public:string removeDuplicates(string s) {// 用string模擬棧string ret;for(auto e : s){if(ret.size() && ret.back() == e) ret.pop_back();else ret.push_back(e);}return ret;}
};

---

2.比較含退格的字符串?

解法1：使用棧來模擬?

? ? ? ? 我們可以封裝一個函數出來，用來處理字符串中的退格符。然后比較處理之后的字符串即可。而處理字符串的過程，就可以使用棧來模擬，如果不是#就入棧，如果遍歷到#就彈出棧頂元素。這一步依舊可以采取string模擬，避免reverse。?

時間復雜度：O(n+m)，n和m分別為s，t的長度，遍歷兩個字符串各一次

空間復雜度：O(m+n)，處理字符串時，最壞情況下兩者都沒有退格符

bool _backspaceCompare(string s, string t) 
{return reBulidString(s) == reBulidString(t);
}string reBulidString(string str)
{string ret;for(auto e : str){if(e == '#' && ret.size()) ret.pop_back();else if(e != '#') ret.push_back(e);}return ret;
}

?解法2：雙指針

? ? ? ? 因為退格符只會對前面的字符產生影響，所以我們可以逆序遍歷字符串。?我們分別定義skipS和skipT來記錄當前的退格次數。如果如果#則skipS++，如果遍歷到普通字符，則看skipST是否為0，如果為0，則表示這個字符肯定會留下來，接著就去遍歷t字符串，找到一個不會被刪除的字符，然后判斷這兩個字符是否相等。如果不相等，則返回false；如果一個字符串為空了，另一個還有，則也返回false。

但是有一種情況需要注意，如果兩個字符串最后一個字符是#，或者最后一個字符被刪除了，此時兩者都越界了，此時返回true。

時間復雜度：O(m+n)

空間復雜度：O(1)

    bool backspaceCompare(string s, string t) {int i = s.size() - 1, j = t.size() - 1;int skipS = 0, skipT = 0;while(i >= 0 || j >= 0) // 這里為什么是或{// 在S中尋找不會被刪除的字符while(i>=0){if(s[i] == '#') skipS++, i--;else if(skipS) skipS--, i--;else break; // 退出該循環說明當前這個字符不會被刪除}// 在T中尋找不會被刪除的字符while(j>=0){if(t[j] == '#') skipT++, j--;else if(skipT) skipT--, j--;else break; // 當前字符不會被刪除}if(i>=0 && j>=0){if(s[i] != t[j]) return false;}else if(i>=0 || j>=0) return false;i--, j--;}return true;}

---

3.基本計算器2?

解法：棧模擬

?????????我們有可能會遇到空格，數字或者運算符，因為優先級的原因，我們如果遇到+/-時不能直接計算，我們采取的策略是將其先放入到棧中，為了避免+/-的運算不同，所以如果是+號，則直接存儲到棧中，如果是-號，則將其相反數壓入棧中。這樣棧中的元素只需要進行加法運算即可。

如果遇到乘號或者除法，則我們直接將后面的數乘或除到棧頂元素上。等遍歷完字符串后，直接將棧中的元素加起來即可。

需要注意的是，數字并不只是一位數，所以我們在遇到數字，需要將后面的數字也提取出來，并且要注意位數。

時間復雜度：O(n)

空間復雜度：O(n)

class Solution 
{
public:int calculate(string s) {   stack<int> calc;// 處理運算符char option = '+'; //第一個數前面的運算符被視為加號for (int i = 0; i < s.size();){// 處理空格if(s[i] == ' '){i++;}else if(isdigit(s[i]))//先獲取數字，數字可能是多位數{int tmp = 0;while(i<s.size() && isdigit(s[i])){tmp = tmp*10 + (s[i++]-'0');}//判斷該數前面的符號是什么// 加減直接將數字壓入棧中，減法壓入負數// 乘除讓棧頂數據*= / /= 上當前的數字if(option == '+') calc.emplace(tmp);else if(option == '-') calc.emplace(-tmp);else if(option == '*') calc.top() *= tmp;else calc.top() /= tmp;}else // 如果是操作符，則更新操作符{option = s[i];i++;}}// 棧中的元素使用加法計算即可int ret = 0;while (!calc.empty()){ret += calc.top();calc.pop();}return ret;}
};

---

4.字符串解碼?

我們在進行解碼的時候要從最內部開始解碼，因為最外層的方括號內部可能還嵌套這其他方括號。

解法：棧+分類討論

? ? ? ? 我們在遍歷字符串的時候，可能遇到數字，左方括號，右方括號，和字母。而我們要分別存儲數字和字母，所以借助兩個棧來實現。

如果遇到數字，我們就提取該數字，因為可能是多位數，所以要循環提取，然后將該數壓入到數字棧中。

如果遇到了左括號，我們接下來就提取字符串，然后壓入到字符棧中。

如果遇到了右括號，說明這是最內層的，此時就可以進行解析。解析之后，我們還得將該結果接到棧頂元素的后面。

如果遇到了字母，則提取該字母，因為該字母并沒有出現在括號中，所以沒有進行重復，直接插入到棧頂元素的后面即可。

細節：因為字符棧有可能為空，這時向棧頂元素后面加上字符就會報錯。所以我們可以提前給棧頂元素壓入一個空串。避免這種情況。

時間復雜度：O(S)，除了遍歷原字符串，每一次解碼都會將其連接到棧頂元素。

空間復雜度：O(S)，解碼后的字符串長度?

class Solution
{
public:string decodeString(string s){stack<int> nst;stack<string> sst;sst.emplace("");int i = 0, n = s.size();while (i < n){// 1.如果遇到數字，則提取數字放入數字棧中if (isdigit(s[i])){int tmp = 0;while (i < n && isdigit(s[i]))tmp = tmp * 10 + (s[i++] - '0');nst.emplace(tmp);}// 2.如果是左括號，則提取左括號后面的字符串else if (s[i] == '['){i += 1;string t;while (i < n && s[i] <= 'z' && s[i] >= 'a')t += s[i++];sst.emplace(t);}// 3.如果是右括號，則拿出兩個棧的棧頂進行解析，并將解析后的結果接到sst棧頂的后面else if (s[i] == ']'){//解析string t;int count = nst.top();nst.pop();while (count--) t += sst.top();sst.pop();//更新sst.top() += t;i++;// 遍歷下一個位置}// 4.如果直接遇到字母，則直接加到字符棧頂元素的后面else{string t;while (i < n && s[i] <= 'z' && s[i] >= 'a')t += s[i++];sst.top() += t;}}return sst.top();}
};

---

5.驗證棧序列?

這道題在學習棧的時候是經常會遇到的一道題，判斷入棧順序能否滿足出棧順序。?

解法：模擬

? ? ? ? 我們按照入棧順序進行入棧，然后判斷棧頂元素與出棧元素是否相等，如果相等，則出棧，然后指針指向下一個出棧元素。如果不相等，則繼續入棧。

如果最后棧為空，則說明滿足，否則不滿足。

時間復雜度：O(n)

空間復雜度：O(n)

class Solution 
{
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;for(int i=0, j=0; i<pushed.size(); ++i){st.emplace(pushed[i]);while(!st.empty() && st.top() == popped[j]){st.pop();j++;}}return st.empty();}
};