如果只了解棧的特點我們可能不知道棧的作用，在大學備考計算機二級C語言的時候，學習過棧和隊列，當時只知道棧的特點是后進先出，隊列的特點是先進先出。編程過程中并沒有用過棧和隊列，沒有體會到算法的巧妙。上了研究生為了找工作開始刷leetcode的題目才體會到算法的巧妙。今天是在俄羅斯的第五個半月，也是我開始刷leetcode的第二遍，這一遍我決定記錄我自己的刷題經驗，以便后來復習，如果能幫助到大家，那更好不過了。

題目一：給定一個只包括 '('，')'，'{'，'}'，'['，']'?的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。

左括號必須以正確的順序閉合。

注意空字符串可被認為是有效字符串。

拿到這個題有可能會想到計算左括號的個數但是這樣空間復雜度會比較大，因為你需要開辟一定的空間來存儲括號的個數。

這個想到用棧還是比較容易的，我們找個棧只存放左括號如果遇到相應的右括號了就出棧，如果最后棧為空就證明全部有效。

class Solution { public:bool isValid(string s) {stack<char>tmp;int len=s.size();if(!len) return true;if(len%2==1) return false;for(int i=0;i<len;i++)//continue 必須有 沒有的化就得if else否則不會進入下個for循環{if(tmp.empty()){tmp.push(s[i]);continue;}if(tmp.top()=='('&&s[i]==')'){tmp.pop();continue;}else if(tmp.top()=='['&&s[i]==']'){tmp.pop();continue;}else if (tmp.top()=='{'&&s[i]=='}'){tmp.pop();continue;}tmp.push(s[i]);//如果輸入連續的兩個左括號沒這句是會出錯的}return tmp.empty();} };

題目二：根據每日 氣溫 列表，請重新生成一個列表，對應位置的輸入是你需要再等待多久溫度才會升高超過該日的天數。如果之后都不會升高，請在該位置用?0 來代替。

例如，給定一個列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應該是 [1, 1, 4, 2, 1, 1, 0, 0]。

拿到這個題對于菜的不行的我來說首先想到就是最笨的辦法。就是拿著數一個一個的去比較。一旦發現一個數大于被比較的數，停止比較，記錄下來這個位置，再減去被比較的數的位置就是題目中求的過幾天才能升到這個溫度，最后一個數不用比較肯定是零。所以首先定義一個和輸入數組一樣大小的數組（初始化為零）來記錄結果。

class Solution { public:vector<int> dailyTemperatures(vector<int>& T) {vector<int> res(T.size());for(int i=0;i<T.size()-1;i++){if(T[i]<100){for(int j=i+1;j<T.size();j++){if(T[j]>T[i]){res[i]=j-i;break;}}}}return res;} };

這個方法確實比較笨但是比較容易想到。耗時也比較長2460毫秒。我們再看一遍程序會發現，我們在拿著數挨個比較的過程中，會有很多的重復，如果我們可以想個辦法去掉這些重復就好了，我想過動態規劃，雙指針（解決數組問題一般就這幾個方法）。能實現，但是效果并不好，參考leetcode上的答案。棧確實比較好實現，這個遞減棧存放的是數組的索引。為什么說它必須是遞減的呢？因為我們目的是找溫度高的值離溫度低的值有多遠。如果溫度低于棧頂元素直接將索引入棧代表我們沒有找到溫度升高的值，如果插入的溫度高于棧頂元素證明我們找到了，然后我們開始出棧計算距離

class Solution { public:vector<int> dailyTemperatures(vector<int>& T) {stack<int> tmp;vector<int>res(T.size());for(int i=0;i<T.size();i++){while(!tmp.empty() && T[i]>T[tmp.top()]){res[tmp.top()]=i-tmp.top();//前面比當前數小的溫度經過幾天才能達到該溫度tmp.pop();//找到經過幾天才能到達溫度就不需要再找了出棧。}tmp.push(i);//把比它小的數pk下去后自己進棧}return res;} };

算法復雜度是O（n），只用了80多毫秒。速度提升了不少阿。這只是幾個數，數越多了提升的效果越明顯。

題目三

給定一個經過編碼的字符串，返回它解碼后的字符串。

編碼規則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正好重復 k 次。注意 k 保證為正整數。

題目三是題目一的擴展，和題目一不同的就是加了數字和字母不再是單純的去找括號是否匹配，如果沒有題目一作為鋪墊，可能更容易想到的是遞歸。有題目一做鋪墊，我們可以去構造兩個棧，一個存放數字，一個存放字母，然后遍歷字符串，遇到 [ 就把數字和字母入棧。代表一個括號內數字和字母組合的開始，遇到] 就把棧頂元素和原來的加（這是精華所在）數字棧和字母棧始終保持只有棧頂元素。

class Solution { public:string decodeString(string s) {stack<string> r;stack<int> d;int num=0;string res;for(int i=0;i<s.size();i++){if(isalpha(s[i]))res.push_back(s[i]);else if(isdigit(s[i])){num=num*10+s[i]-'0'; //需要特別注意的一點減'0'因為是字符串里的值 *10的原因是連續的數字}else if(s[i]=='['){r.push(res);res="";d.push(num);num=0;}else{for(int j=0;j<d.top();j++)r.top()+=res;d.pop();res=r.top();r.pop();}}return res;} };

個人總結：涉及到數組相關需要數組內的數有次序或者需要配對的數組均可以通過單調棧來解決問題。

配對問題： 括號匹配（單純括號、數字和括號組合）

次序：接雨水 求柱狀圖中最大矩形

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

這個題的關鍵就是構建一個遞增棧當遇到一個數比棧頂元素小時，就開始出棧，出棧元素是高，寬是當前元素減去出棧元素前一個的索引（因為先出的棧實際減去的是棧頂元素的前一個值多減了所以需要再減去一個）。當插入的元素大于棧中的元素時直接入棧。

class Solution { public:int largestRectangleArea(vector<int>& nums) {stack<int> s;nums.push_back(0);//是哨兵 即在數組元素最后又加了一個零，對結果沒什么影響int max1=0;for(int i=0;i<nums.size();++i){while(!s.empty()&&nums[i]<=nums[s.top()]){int top=s.top();s.pop();max1=max(max1,nums[top]*(s.empty()?i:i-s.top()-1));}s.push(i);}nums.pop_back();//哨兵循環到最后方便出棧return max1;} };

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的栈的应用（c++）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。