代码随想录算法训练营第63天|84.柱状图中最大的矩形

84.柱状图中最大的矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> minLeft(heights.size());
        vector<int> minRight(heights.size());
        minLeft[0] = -1;
        for (int i = 1; i < heights.size(); i++) {
            int index = i - 1;
            while (index >= 0 && heights[index] >= heights[i]) index = minLeft[index];
            minLeft[i] = index;
        }
        minRight[heights.size() - 1] = heights.size();
        for (int i = heights.size() - 2; i >= 0; i--) {
            int index = i + 1;
            while (index < heights.size() && heights[index] >= heights[i]) index = minRight[index];
            minRight[i] = index;
        }
        int result = 0;
        for (int i = 0; i < heights.size(); i++) {
            int s = (minRight[i] - minLeft[i] - 1) * heights[i];
            if (s > result) result = s;
        }
        return result;
    }
};