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

(单调栈，枚举) O ( n ) O(n) O(n) 列出每个高度。对于每个高度，我们可以找到高度左右的第一个低于高度的索引。当我们找到左右第一个低于高度的索引时，我们可以维护一个单调的栈，找到当前高度低于一侧的高度索引值

对于左右两侧使用单调栈找到第一个低于当前高度的高索引值，我们只经历一次数组，最终找到两侧的时间复杂性是 O ( 2 n ) O(2n) O(2n)，最后，每个高度的时间复杂度也是如此 O ( n ) O(n) O(n)，最终时间的复杂性是 O ( n ) O(n) O(n)。

C 代码

class Solution { 
         public:     int largestRectangleArea(vector<int>& heights) { 
                 stack<int> s;         int n = heights.size();         vector<int> l(n), r(n);         for(int i = n - 1; i >= 0; i --)         { 
                     int t = heights[i];             while(s.size() && heights[s.top()] >= t) s.pop();
            r[i] = s.size() == 0 ? n : s.top();
            s.push(i);
        }
        stack<int> q;
        for(int i = 0; i < n; i ++)
        { 
        
            int t = heights[i];
            while(q.size() && heights[q.top()] >= t) q.pop();
            l[i] = q.size() == 0 ? -1 : q.top();
            q.push(i);
        }

        int res = 0;
        for(int i = 0; i < n; i ++)
        { 
        
            res = max(res, (r[i] - l[i] - 1) * heights[i]);
        }
        return res;
    }
};