单调栈.md

单调栈是用来保持一种单调递增或者单调递减的栈

一般用在寻找一个元素左边或者右边第一个比自己大/小的位置时使用

找第一个小用单增栈，找第一个大用单减栈

由于每个元素最多进栈一次，复杂度O（n）

//模版
stack<int> s;
vector<int> ans(n)
for(int i=0;i<n;i++){
  	while(!s.empty() && a[i]>a[s.top()]){
      	ans[s.top()] = i - s.top();
      	s.pop();
    }
  	s.push(i);
}

//单调栈解决最大矩形面积
给定一个数组a，表示底为1，高为a[i]的矩形，求在该柱状图中，能够勾勒出来的矩形的最大面积
暴力：两层for循环遍历底或者高，复杂度: O(n^2)
优化：遍历高时，常规做法是对于每一个下标i对应的高，分别向两边拓展，知道两边第一个小于a[i]
  	 可以用单调栈存储每次找左右两边第一个小的
vector<int> l(n),r(n);
stack<int> s;
for(int i=0;i<n;i++){
  	if(!s.empty() && a[s.top()] >= a[i]){
      	s.pop();
    }
  	l[i] = s.empty()? -1: s.top();
  	s.push(i);
}
for(int i=n-1;i>=0;i--){
  	if(!s.empty() && a[s.top()] >= a[i]){
      	s.pop();
    }
  	r[i] = s.empty()? n: s.top();
  	s.push(i);
}
int ans = 0;
for(int i=0;i<n;i++){
  	ans = max(ans,a[i]*(r[i]-l[i]-1));
}