c/c++语言开发共享51nod 1102 面积最大的矩形（单调栈）

51nod 1102 面积最大的矩形（单调栈）

以i所指的矩形高度作为要组成的矩形的高度，分别向左右扩展。用单调栈维护一个left数组和一个right数组，记录向左右能扩展到的边界，然后扫一遍出结果。

  #include   #include   #include   using namespace std;    const int maxn = 5e4+10;  long long num[maxn];  int lt[maxn],rt[maxn];    int main()  {      int n;      cin >> n;      num[1] = 0;      for(int i = 2; i <= n+1; ++i)          cin >> num[i];      num[n+2] = 0;      n += 2;      stack s1,s2;      for(int i = 1; i <= n; ++i)      {          while(s1.size() && num[s1.top()] >= num[i])              s1.pop();          if(s1.size()) lt[i] = s1.top()+1;          else lt[i] = i;          s1.push(i);      }      for(int i = n; i >= 1; --i)      {          while(s2.size() && num[s2.top()] >= num[i])              s2.pop();          if(s2.size()) rt[i] = s2.top()-1;          else rt[i] = i;          s2.push(i);      }      long long res = 0;      for(int i = 1; i <= n; ++i)          res = max(res,(rt[i]-lt[i]+1)*num[i]);      cout << res << endl;      return 0;  }