单调栈

下一个更大的元素

• 直接用单调递增的栈来求出每一个点最近大于该点的值
• 用k-y来存该点下一个更大的值，遍历询问就行。

  #include <iostream>
  #include <unordered_map>
  #include <stack>
  using namespace std;
  const int maxn=1005;
  int numa[maxn];
  int numb[maxn];
  unordered_map<int,int> ans;
  stack<int> st;
  int main() {
  //    freopen("a.txt","r",stdin);
      int   n,m;
      cin>>n>>m;
      for (int i=0;i<n;i++) cin>>numa[i];
      int temp;
      for (int i=0;i<m;i++) {
          cin>>temp;
          if ( st.empty() ) st.push(temp);
          else {
  //            if ( temp > st.top() ) {
  //                ans[st.top()]=temp;
  //                st.pop();
  //            }
              while ( !st.empty() && temp>st.top() ) {
                  ans[st.top()]=temp;
                  st.pop();
              }
              st.push(temp);
          }
      }
      for (int i=0;i<n;i++) {
          if( ans[numa[i]] > numa[i] ) cout<<ans[numa[i]]<<" ";
          else printf("-1 ");
      }
      return 0;
  }

  最大矩形面积
• width+1 保证到第i点时，从i-1点开始向前计算时 加上了i点的长度，计算矩形面积是不包括i点

int s[];//stack
int a[];//高度
int w[];//记录已经出栈的连续矩形长度，
int p=0;
long long ans=0;
a[n=1]=0;//在最后添加一个矮的矩形，保证最后几个还在栈中（高度递增）的矩形出栈来更新ans
for (int i=1;i<=n+1;i++) {
    if ( a[i] > s[p] ) {//栈保证单调递增
        s[++p] = a[i];//入栈
        w[p]=1;//记录在栈中的索引，因为该点会被用来更新ans,初始化为1,记录该点到下一个i点之间已经出栈的值
    } else {
        int width=0;
        while ( a[i] < s[p] ) {
            width += w[p];//从p-1的矩形开始计算面积
            ans = max(ans,(long long)width*s[p]);
            p--;
        }
        s[++p]=a[i];
        w[p] = width + 1；//此次更新ans,删除的中间高度连续的矩形长度,+下一次的i点的长度
    }
}
printf("%lld",ans);