先思考一个问题：给你一列数字，对每个数字求出其右边第一个值大于等 于它的数字的位置。要求做到线性。
如果暴力枚举那复杂度是O(n^2)，那花费算是相当大的，我们可以用一个栈来维护这个队列，只扫描一次数据就可以达到目的。
具体操作：把数据压入栈中，如果这个数据大于（或者小于）栈顶元素，那就pop栈顶元素，这样操作n次。这样就维护了一个单调减栈（单调增栈）
通俗一点，一群人在排队，硬气度分别为（1 4 2 3 5），按顺序排队，硬气度低的害怕硬气度高的，只要硬气度高的在硬气度低的后面，就会被吓走。
下面是过程（括号中代表硬气值，括号外的数字是下标）：下标为1（1）的人排队，2（4）进入，1（1）害怕而逃走并且记住了2（4），目前排队的只有2（4），3（2）进入，无事发生，4（3）进入，3（2）害怕逃走并记住了，目前排队的只有2（4） 4（3），5（5）进入，2（4） 4（3）害怕并且记住了5（5）。
下面是实现代码：
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
int a[3000010];
int ans[3000010];
stack <int>s;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}//读入数据
for(int i=1;i<=n;i++){
while(!s.empty()&&a[i]>a[s.top()]){//如果前面的硬气值高，那就逃并且记住。
ans[s.top()]=i; // 记住
s.pop();// 逃
}
s.push(i); //接着排队
}
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);//输出
}
}下面有一道题
有一列n个数字a[1]…a[n]，对所有1<=L<=R<=n求max(a[L],a[L+1],…,a[R]) 并求和，n<=1e6（1s）
很显然就是找一个离着a[x]最近的比他大的数字，先考虑所有数字互不相同的情况。
考虑数字a[p]会成为哪些区间的max，用上文方法求出左面和右面第一个比它大的位置l[p]和r[p]（认为a[0]和a[n+1]是正无穷即可避免一些特判）。
那么当 l[p]<=L<=R<r[p]时，有max(a[L],…,a[R])=a[p]，所以很显然答案就是a[p]*(pl[p])*(r[p]-p)的和。
那么如果有相同数字的话，要假设左边的比右边的大。
还有一道题：考虑有一列n个数字，求1<=L<=R<=n使得(R-L+1)*min(a[L],a[L+1],…,a[R]) 最大。n<=1000000。
很显然还是和刚才一样对每个数字维护其在哪个极大区间成为最小值，然后L,R取 为这个区间算一算即可。
扩展：有一个矩阵，每个位置是0或者1。求最大的全1子矩阵。n*m<=1000000
思路：对每个位置维护其向上极长的1的段的长度，然后每行转化为刚刚那个问题即可。