1. C棧與隊列OJ題核心解析在算法競賽和編程面試中棧(stack)和隊列(queue)是最基礎也最常考的數(shù)據(jù)結構。最近在幫學員復盤OJ題庫時我發(fā)現(xiàn)80%的棧隊列問題都集中在以下五類場景括號匹配、表達式求值、滑動窗口、二叉樹遍歷和單調棧應用。掌握這些題型的固定解法能快速提升解題效率。2. 棧的典型應用場景2.1 括號匹配問題LeetCode 20題有效的括號是經典例題。核心思路是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(); }關鍵點在于遇到右括號時檢查棧頂元素是否匹配。時間復雜度O(n)空間復雜度O(n)。2.2 表達式求值中綴表達式轉后綴表達式逆波蘭式是棧的經典應用。以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)時間解決。標準解法是單調隊列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; }隊列中存儲的是下標而非值這樣可以方便判斷窗口范圍。每個元素最多入隊出隊各一次均攤時間復雜度O(1)。3.2 二叉樹層序遍歷LeetCode 102題是隊列的典型應用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; }注意要先記錄當前隊列大小再處理因為處理過程中隊列長度會變化。4. 單調棧進階技巧4.1 柱狀圖中最大矩形LeetCode 84題的單調棧解法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題的單調棧解法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; }這里棧中存儲的是下標通過下標差計算等待天數(shù)。時間復雜度O(n)。5. 常見錯誤與調試技巧?？张袛噙z漏在pop()或top()前務必檢查!stack.empty()優(yōu)先級混淆表達式求值時注意*/優(yōu)先級高于-下標越界滑動窗口問題要仔細計算窗口范圍類型轉換錯誤字符串轉數(shù)字時使用stoi而非atoi內存泄漏C中手動new的節(jié)點要記得delete調試時可以打印棧/隊列內容void printStack(stackint s){ while(!s.empty()){ couts.top() ; s.pop(); } coutendl; }對于復雜問題建議先在紙上畫出棧/隊列的變化過程。例如處理[()]{}{ ()() }時可以逐步記錄棧的狀態(tài)變化。