1. C棧與隊列OJ題核心解析在算法競賽和編程面試中棧(stack)和隊列(queue)是最基礎(chǔ)也最?？嫉臄?shù)據(jù)結(jié)構(gòu)。最近在幫學(xué)員復(fù)盤OJ題庫時我發(fā)現(xiàn)80%的棧隊列問題都集中在以下五類場景括號匹配、表達式求值、滑動窗口、二叉樹遍歷和單調(diào)棧應(yīng)用。掌握這些題型的固定解法能快速提升解題效率。2. 棧的典型應(yīng)用場景2.1 括號匹配問題LeetCode 20題有效的括號是經(jīng)典例題。核心思路是bool isValid(string s) { stackchar st; for(char c : s){ if(c(||c[||c{) st.push(c); else { if(st.empty()) return false; char top st.top(); if((c)top!() || (c]top![) || (c}top!{)) return false; st.pop(); } } return st.empty(); }關(guān)鍵點在于遇到右括號時檢查棧頂元素是否匹配。時間復(fù)雜度O(n)空間復(fù)雜度O(n)。2.2 表達式求值中綴表達式轉(zhuǎn)后綴表達式逆波蘭式是棧的經(jīng)典應(yīng)用。以LeetCode 150題為例int evalRPN(vectorstring tokens) { stackint st; for(string s : tokens){ if(s||s-||s*||s/){ int b st.top(); st.pop(); int a st.top(); st.pop(); if(s) st.push(ab); else if(s-) st.push(a-b); else if(s*) st.push(a*b); else st.push(a/b); } else st.push(stoi(s)); } return st.top(); }注意處理負數(shù)除法的截斷問題建議使用a/b 0 ? floor(1.0*a/b) : ceil(1.0*a/b)。3. 隊列的高頻考點3.1 滑動窗口最大值LeetCode 239題要求用O(n)時間解決。標(biāo)準解法是單調(diào)隊列vectorint maxSlidingWindow(vectorint nums, int k) { dequeint q; vectorint res; for(int i0;inums.size();i){ while(!q.empty()nums[q.back()]nums[i]) q.pop_back(); q.push_back(i); if(q.front()i-k) q.pop_front(); if(ik-1) res.push_back(nums[q.front()]); } return res; }隊列中存儲的是下標(biāo)而非值這樣可以方便判斷窗口范圍。每個元素最多入隊出隊各一次均攤時間復(fù)雜度O(1)。3.2 二叉樹層序遍歷LeetCode 102題是隊列的典型應(yīng)用vectorvectorint levelOrder(TreeNode* root) { queueTreeNode* q; vectorvectorint res; if(root) q.push(root); while(!q.empty()){ int size q.size(); vectorint level; while(size--){ TreeNode* cur q.front(); q.pop(); level.push_back(cur-val); if(cur-left) q.push(cur-left); if(cur-right) q.push(cur-right); } res.push_back(level); } return res; }注意要先記錄當(dāng)前隊列大小再處理因為處理過程中隊列長度會變化。4. 單調(diào)棧進階技巧4.1 柱狀圖中最大矩形LeetCode 84題的單調(diào)棧解法int largestRectangleArea(vectorint heights) { heights.push_back(0); stackint st; int res 0; for(int i0;iheights.size();){ if(st.empty()||heights[i]heights[st.top()]){ st.push(i); } else { int h heights[st.top()]; st.pop(); int w st.empty() ? i : i-st.top()-1; res max(res, h*w); } } return res; }技巧是在數(shù)組末尾補0保證所有元素都能被處理到。計算寬度時要注意空棧的情況。4.2 每日溫度問題LeetCode 739題的單調(diào)棧解法vectorint dailyTemperatures(vectorint T) { stackint st; vectorint res(T.size()); for(int i0;iT.size();i){ while(!st.empty()T[i]T[st.top()]){ res[st.top()] i-st.top(); st.pop(); } st.push(i); } return res; }這里棧中存儲的是下標(biāo)通過下標(biāo)差計算等待天數(shù)。時間復(fù)雜度O(n)。5. 常見錯誤與調(diào)試技巧?？张袛噙z漏在pop()或top()前務(wù)必檢查!stack.empty()優(yōu)先級混淆表達式求值時注意*/優(yōu)先級高于-下標(biāo)越界滑動窗口問題要仔細計算窗口范圍類型轉(zhuǎn)換錯誤字符串轉(zhuǎn)數(shù)字時使用stoi而非atoi內(nèi)存泄漏C中手動new的節(jié)點要記得delete調(diào)試時可以打印棧/隊列內(nèi)容void printStack(stackint s){ while(!s.empty()){ couts.top() ; s.pop(); } coutendl; }對于復(fù)雜問題建議先在紙上畫出棧/隊列的變化過程。例如處理[()]{}{ ()() }時可以逐步記錄棧的狀態(tài)變化。