单调栈 ---[ 数据结构 ]

单调栈

定义

1. 单调栈就是 栈内元素单调递增 或者 单调递减的 栈
2. 并且只能在栈顶操作 （入栈和出栈）
3. 单调栈的维护是O(n)的时间复杂度，所有元素只会 进栈一次

解题基本思想

用途：用于求 从左/右 遍历 得到第一个 比 它 小/大的元素的位置

元素  在出栈时 考虑 右侧边界（即右侧边界不符条件时 ，元素出栈）
         在入栈时 考虑 左侧边界 （栈内为单调序列，左侧边界相对固定）

实现方式

1.单调递增栈 ： 从栈底到 栈顶 元素 序列单调 递增 （栈顶为 最大值）
  作用：获取离当前位置最近的一个小于当前值的元素的 位置。
（也可确定某个元素 在 一定长度 的 区间中 做最小值 ）
2.单调递减栈 ： 从栈底到 栈顶 元素 序列单调 递减 （栈顶为 最小值）
  作用：获取离当前位置最近的一个大于当前值的元素的 位置。
（也可确定某个元素 在 一定长度 的 区间中 做最大值 ）

/*
* 单调 递增栈
*/
stack<int > s;
for(int i=0;i<n;i++)
{
while(!s.empty()&&a[s.top()]>a[i])
// 维护 递增栈
{
// 对s.top() 的相关元素 进行操作
s.pop();
}
s.push(i);
}

/*
* 单调 递减栈
*/
stack<int > s;
for(int i=0;i<n;i++)
{
while(!s.empty()&&a[s.top()]<a[i])
// 维护 递减栈
{
// 对s.top() 的相关元素 进行操作
s.pop();
}
s.push(i);
}

直方图的最大矩阵面积 （hdu 1506）

思路：
最大面积值 是以 某个矩形的 高度为最大 高度
宽为 该矩形 左右 第一个 小于 其 高度的 元素位置 之差 ，（相乘 得到最大面积）

注意：

1. 左边界 没有元素的 初始 值 为 -1 ，右边界 在 出栈时得到，
   左边界 -1 为初始值的原因是 左边界 不会算在面积中， 计算为 左边界+1
   宽度=右边界-（左边界+1）；

下面提供两种 不同的码风

long long
maxArea(vector<int > height)
{
stack<int> s;
height.push_back(0);
// 简化代码 ，保证单调 递增栈 最后 站内元素会清空
long long
ans=0;
for(int i=0; i<height.size(); i++)
{
while(!s.empty()&&height[s.top()]>height[i])
{
int h=height[s.top()];
s.pop();
int leftId= !s.empty()? s.top(): -1;
int w=i-(leftId+1);
ans=max(ans,(long long )h*w);
}
s.push(i);
}
return ans;
}

long long maxArea1(vector<int > height)
{
stack<int >s;
int n=height.size();
vector<int> right(n,n),left(n,-1);
for(int i=0; i<n; i++)
{
while(!s.empty()&&height[s.top()]>height[i])
{
right[s.top()]=i;
s.pop();
}
if(!s.empty())
{
left[i]=s.top();
}
s.push(i);
}
for(int i=0;i<n;i++)
printf("%d %dn",left[i],right[i]);
long long ans=0;
for(int i=0;i<n;i++)
{
ans=max(ans,(long long )height[i]*(right[i]-(left[i]+1)));
}
return ans;
}

最后

以上就是务实香烟为你收集整理的单调栈 ---[ 数据结构 ]的全部内容，希望文章能够帮你解决单调栈 ---[ 数据结构 ]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。