算法与数据结构基础 - 堆栈(Stack)
算法与数据结构基础 – 堆栈(Stack)
2019-07-05 15:52 by bangerlee, … 阅读, … 评论, 收藏, 编辑
堆栈基础
堆栈(stack)具有“后进先出”的特性，利用这个特性我们可以用堆栈来解决这样一类问题：后续的输入会影响到前面的阶段性结果。线性地遍历输入并用stack处理，这类问题较简单，求解时间复杂度一般为O(n)。
相关LeetCode题：
844. Backspace String Compare 题解
1047. Remove All Adjacent Duplicates In String 题解
150. Evaluate Reverse Polish Notation 题解
堆栈处理嵌套关系
堆栈还可以用于解决嵌套类问题，例如 LeetCode 856. Score of Parentheses，时间复杂度O(n)：
//856. Score of Parentheses int scoreOfParentheses(string S) { stack<int> st; st.push(0); //最终结果 for(char c:S){ if(c=='(') st.push(0); //暂存中间结果 else{ int val=st.top();st.pop(); val=st.top()+max(val*2,1); st.pop(); //更新中间和最终结果 st.push(val); } } return st.top(); }
这类问题的难点在于理解嵌套过程，分析在单个嵌套开始时如何用stack暂存状态、对应嵌套结束时如何更新状态。嵌套问题一般也可以使用递归求解，递归解法理解起来比堆栈解法更直观：直至嵌套的中心、层层往外处理。
相关LeetCode题：
856. Score of Parentheses 堆栈题解 递归题解
341. Flatten Nested List Iterator 题解
636. Exclusive Time of Functions 题解
单调栈
形如这样的问题也可用堆栈解决：对一个数组，对每个元素求大于或小于该元素的下一个数，例如 LeetCode 503. Next Greater Element II：
//503. Next Greater Element II vector<int> nextGreaterElements(vector<int>& nums) { vector<int> res(nums.size(),-1); stack<int> st; for(int i=nums.size()-1;i>=0;i--) st.push(i); for(int i=nums.size()-1;i>=0;i--){ while(!st.empty()&&nums[i]>=nums[st.top()]) st.pop(); if(!st.empty()) res[i]=nums[st.top()]; st.push(i); } return res; }
以上堆栈形式叫单调栈(monotone stack)，栈内元素单调递增或递减，用其可以实现O(n)时间复杂度求解问题。
相关LeetCode题：
503. Next Greater Element II 题解
1063. Number of Valid Subarrays 题解
1019. Next Greater Node In Linked List 题解
84. Largest Rectangle in Histogram 题解