C++ 解法, 执行用时: 15ms, 内存消耗: 2976KB, 提交时间: 2022-01-22

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        int max_area = 0;
        heights.push_back(0);
        stack<int> cache;
        for (int i = 0; i < heights.size(); ++i) {
            while (!cache.empty() && heights[cache.top()] >= heights[i]) {
                int cur_index = cache.top();
                cache.pop();
                int length = cache.empty() ? i : i - cache.top() - 1;
                int cur_area = heights[cur_index] * length;
                max_area = max(max_area, cur_area);
            }
            cache.push(i);
        }
        return max_area;
    }
};

C++ 解法, 执行用时: 15ms, 内存消耗: 3568KB, 提交时间: 2021-11-17

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        // write code here
        heights.push_back(-1);
        stack<int> s;
        int maxn = 0;
        for (int i = 0; i < heights.size(); i++) {
            if (s.empty() || heights[s.top()] <= heights[i]) s.push(i);
            else {
                int top;
                while (!s.empty() && heights[s.top()] > heights[i]) {
                    top = s.top(); s.pop();
                    maxn = max(maxn, heights[top] * (i - top));
                }
                s.push(top);
                heights[top] = heights[i];
            }
        }
        return maxn;
    }
};

C++ 解法, 执行用时: 16ms, 内存消耗: 2960KB, 提交时间: 2021-11-29

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        // write code here
        
    stack<int> sta;
    sta.push(-1);
    int maxArea = 0;
    for (int i = 0; i < heights.size(); ++i)
    {
        while (sta.top() != -1 && heights[sta.top()] >= heights[i])
        {
            int height = heights[sta.top()];
            sta.pop();
            int width = i - sta.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        sta.push(i);
    }

    while (sta.top() != -1)
    {
        int height = heights[sta.top()];
        sta.pop();
        int width = heights.size() - sta.top() - 1;
        maxArea = max(maxArea, height * width);
    }
    return maxArea;
        
    }
};

C++ 解法, 执行用时: 16ms, 内存消耗: 2976KB, 提交时间: 2022-02-19

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        // write code here
        stack<int> s;
        heights.push_back(0);
        heights.insert(heights.begin(), 0);
        int res = 0;
        for(int i = 0;i < heights.size();i++){
            while(!s.empty() && heights[s.top()] > heights[i]){
                int t = s.top();
                s.pop();
                int l = s.top() + 1;
                int r = i - 1;
                res = max(res,heights[t] * (r - l + 1));
            }
            s.push(i);
        }
        return res;
    }
};

C++ 解法, 执行用时: 17ms, 内存消耗: 2968KB, 提交时间: 2022-03-15

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> s;
        vector<int> left(n);
        vector<int> right(n, n);
        
        for (int i = 0; i < heights.size(); i++) {
            while (!s.empty() && heights[s.top()] >= heights[i]) {
                right[s.top()] = i;
                s.pop();
            }
            left[i] = s.empty() ? -1 : s.top();
            s.push(i);
        }
        
        int maxarea = 0;
        for (int i = 0; i < heights.size(); i++) {
            int area = heights[i] * (right[i] - left[i] - 1);
            maxarea = max(maxarea, area);
        }
        return maxarea;
    }
};