LeetCode 84.柱状图中最大的矩形

#define N 100005
class Solution {
public:
    //求arr中元素左边第一个更小元素的下标，保存到left
    void getLeft(vector<int> &arr,vector<int> &left)
    {
        int n=arr.size();
        int st[N],top=-1;
        for(int i=0;i<n;i++)
        {
            while(top>=0&&arr[st[top]]>arr[i])
            {
                top--;
            }
            if(top>=0) left[i]=st[top];
            top++,st[top]=i;
        }
        return;
    }
    //求arr中元素右边第一个更小元素的下标，保存到right
    void getRight(vector<int> &arr,vector<int> &right)
    {
        int n=arr.size();
        int st[N],top=-1;
        for(int i=0;i<n;i++)
        {
            while(top>=0&&arr[st[top]]>arr[i])
            {
                right[st[top]]=i,top--;
            }
            top++,st[top]=i;
        }
        return;
    }
    int largestRectangleArea(vector<int>& heights) {
        heights.emplace(heights.begin(),0);
        heights.emplace_back(0);
        int ans=0,n=heights.size();
        vector<int> l(n),r(n);
        getLeft(heights,l);
        getRight(heights,r);
        for(int i=0;i<n;i++)
        {
            ans=max(ans,heights[i]*(r[i]-l[i]-1));
        }
        return ans;
    }
};