笔试刷题-美团2018-08-01

题目描述：

/**
给定一组非负整数组成的数组h，代表一组柱状图的高度，
其中每个柱子的宽度都为1。
在这组柱状图中找到能组成的最大矩形的面积（如图所示）。
入参h为一个整型数组，代表每个柱子的高度，返回面积的值。
输入描述:
输入包括两行,第一行包含一个整数n(1 ≤ n ≤ 10000)
第二行包括n个整数,表示h数组中的每个值,h_i(1 ≤ h_i ≤ 1,000,000)
输出描述:
输出一个整数,表示最大的矩阵面积。
输入例子1:
6
2 1 5 6 2 3
输出例子1:
10
*/

思路如下：

维护一个单调递增的堆
更新left[i]表示i位置向左可以延伸多少
right[i]同理

代码如下：

#include<stdio.h>
#include<iostream>
#include<climits>
#include<stack>
 
#define MAX_N 10005
 
typedef long long ll;
 
using namespace std;
 
int height[MAX_N], lnum[MAX_N], rnum[MAX_N];
 
int main(){
    int n;
    stack<int> st;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", height+i);
    lnum[0] = 0;
    for(int i=0; i<n; i++){
        if(st.empty() || height[i]>height[st.top()]){
            st.push(i);
        }
        else{
            while(!st.empty() && height[i]<=height[st.top()])
                st.pop();
            if(st.empty())
                lnum[i] = i;
            else
                lnum[i] = i-1-st.top();
            st.push(i);
        }
    }
    //清空
    while(!st.empty())
        st.pop();
    rnum[n-1] = 0;
    for(int i=n-1; i>=0; i--){
        if(st.empty() || height[i]>height[st.top()]){
            st.push(i);
        }
        else{
            while(!st.empty() && height[i]<=height[st.top()])
                st.pop();
            if(st.empty())
                rnum[i] = n-(i+1);
            else
                rnum[i] = st.top()-i-1;
            st.push(i);
        }
    }
    ll res = LLONG_MIN;
    for(int i=0; i<n; i++){
        res = max(res, (ll)(lnum[i]+rnum[i]+1)*(ll)height[i]);
    }
    printf("%lld", res);
    return 0;
}