[数据结构与算法]Leetcode 84.柱状图中最大的矩形

原题链接 ：Leetcodet原题链接

算法

(单调栈,枚举) $O(n)$
枚举每一个高度，对于每一个高度，分别找出该高度左右第一个小于该高度的索引，在找出左右第一个小于高度的索引时，我们可以维护一个单调栈来找当前高度在其中一侧的小于该高度的高度索引值

时间复杂度

对于左右侧利用单调栈来找第一个小于目前高度的高度索引值，我们只会遍历一次数组，最终找两侧的时间复杂度为$O(2n)$，最后枚举每个高度的时间复杂度也是$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;
    }
};