柱状图中最大的矩形

题目链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/submissions/
题目描述：

题解：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> minLeft(heights.size(), 0);
        vector<int> minRight(heights.size(), 0);
        //记录每个节点左边第一个小于当前节点的下标
        minLeft[0] = -1;
        for(int i = 1; i < heights.size(); i++)
        {
            int t = i -1;
            while(t >= 0 && heights[t] > heights[i])
            {
                t = minLeft[t];
            }
            minLeft[i] = t;
        }
        //记录每个节点右边第一个小于当前节点的下标
        minRight[heights.size() - 1] = heights.size();
        for(int i = heights.size() - 2; i >= 0; i--)
        {
            int t = i + 1;
            while(t < heights.size() && heights[t] >= heights[i])
            {
                t = minRight[t];
            }
            minRight[i] = t;
        }
        int result = 0;
        for(int i = 0; i < heights.size(); i++)
        {
            int sum = heights[i] * (minRight[i] - minLeft[i] - 1);
            result = max(sum, result);

        }
        return result;

    }
};