笔者最近在刷 LeetCode 习题，故想将一些经典算法以及一些经典的数据结构汇编成一个系列，分享给大家和当前的本人。本文次要波及 枯燥栈。
枯燥栈
枯燥栈自身的概念并不难理解，然而理论利用起来须要了解粗浅才行。笔者当初了解了一个早晨才弄明确，而你们只须要看完这半篇文章即可齐全了解。
对于递增栈和递加栈很多中央说法不一，此处为了不便阐明，将栈底到栈顶枯燥增的即为递增栈；枯燥减的即为递加栈。（不肯定正确，然而不影响之后的了解）。
先探讨递增栈，此处我定义一个概念：极左邻元素和极右邻元素。假如数组 nums，其中以后元素的下标为 k，那么若满足 nums[q] < nums[k]，且在区间 [q+1,k-1] 中的元素全都大于 nums[k]。那么 nums[q]即为 nums[k]的极左邻元素，同理能够定义极右邻元素。
递加栈中相似，此处不再赘述。
光看下面的定义的确很好了解，让咱们来思考一下枯燥栈的作用。它可能帮忙咱们找到以后元素的极左邻元素和极右邻元素，从而实现一些性能。搬一道经典题目，
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
给定 n 个非负整数，用来示意柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，可能勾画进去的矩形的最大面积。
图中暗影局部为所能勾画出的最大矩形面积，其面积为
10个单位。
此题若采纳暴力搜寻的形式诚然很简单，其实用枯燥栈即可在 O（n）的工夫内解决。大家先了解一个“扩散”的概念，假如我当初抉择倒数第二个柱子（值为 2），要想以此为核心，勾画出最大的矩形，那么从这个柱子开始，左右扩散。右边的柱子比本人高，扩散胜利，左边的柱子也比本人高，扩散胜利。所以最终能够扩散到 [5,6,2,3] 这几根柱子上，那么以以后这个柱子为高，所能勾画最大矩形面积即为 2 *4 = 8。那么这种“扩散”是在哪里进行的呢？显然，是在比以后元素小的且离以后元素最近的元素进行，这不就是上文中提到的 极左邻元素 嘛！所以只有能确定每个元素的极左邻元素和极右邻元素，那么间接一减就是宽度了呀。
如何利用枯燥栈找极左邻、极右邻元素？
保护一个递增栈。留神：栈中放的是元素的下标。要获取元素比大小的话，间接通过下标去数组中找就好了。
枯燥栈的代码模板
int stack_F(vector<int>& nums){
int maxx;
stack<int>st;
// 此处的 - 1 是比 nums 中所有数都要小的数，也能够 -1000，本人定。次要是为了让栈中的所有元素都能够被弹出，因为要保护枯燥栈，遇到一个很小的数，栈中的元素必定全都会被弹出来。有利于将所有解都遍历到。nums.push_back(-1);
for(int i=0;i<nums.size();i++){
// 此处等号可取可不取
if(st.empty() || nums[st.top()] <= nums[i]){
// 存的是下标哦！st.push(i);
}
else{while(!st.empty() && nums[st.top()] > nums[i]){
// 留神你是站在栈顶元素的立场来看的喔！int index = st.top();st.pop();
int left_boder = st.top();
int right_boder = i;
// 有了这些边界点，就能够自定义统计左右符合条件的数量啦！比拟 maxx 的值等。//your code ...
}
st.push(nums[i]);
}
}
return maxx;
}至此 枯燥栈 就完结了，下次更新的主题《递归的好基友，动静布局？啥是无后效性？》，欢送点赞珍藏！