leetcode 84 柱状图中最大的矩形

题目

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

 

C++代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st; //递增栈,存下标
        int res= 0;
        int i = 0, n = heights.size();
        while(i < n)
        {
            if(st.empty() || heights[i] >= heights[st.top()])
            {
                st.push(i);
                i++;
            }
            else
            {
                int k = st.top();
                st.pop();
                if(st.empty())
                    res = max(res, heights[k] * (i - 0));
                else
                    res = max(res, heights[k] * (i - st.top() - 1));
            }
        }
        while(!st.empty())
        {
            int k = st.top();
            st.pop();
            if(st.empty())
                res = max(res, heights[k] * (i - 0));
            else
                res = max(res, heights[k] * (i - st.top() - 1));
        }
        return res;
    }
};

 

上一篇:84.最大面积,85.直方图中最大矩形


下一篇:arcgis80坐标转84坐标方法