C++ day60 柱状图中最大的矩形

题目1：84 柱状图中最大的矩形

题目链接：柱状图中最大的矩形

对题目的理解

n个非负整数，表示柱状图中各个柱子的高度，每个柱子的宽度为1，求柱状图中能够勾勒出的矩形的最大面积。

本题和昨天的接雨水的题目一样，需要找到3个柱子，基准柱子，左边比他小的柱子，右边比他小的柱子

暴力解法（按列，纵向）

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int sum=0;
        for(int i=0;i<heights.size();i++){
            int left=i;
            int right=i;
            for(;left>=0;left--){
                if(heights[left]<heights[i]) break;
            }
            for(;right<heights.size();right++){
                if(heights[right]<heights[i]) break;
            }
            int w=right-left-1;
            int h=heights[i];
            int s=h*w;
            sum=max(sum,s);
        }
        return sum;
    }
};

以上代码会超时

双指针（按列，纵向）

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int sum=0;
        vector<int> leftheight(heights.size(),0);
        vector<int> rightheight(heights.size(),0);
        leftheight[0]=-1;
        for(int i=1;i<heights.size();i++){
            int t=i-1;
            //不断向左寻找
            while(t>=0&&heights[t]>=heights[i]) t=leftheight[t];
            leftheight[i] = t;
        }
        rightheight[heights.size()-1]=heights.size();
        for(int i=heights.size()-2;i>=0;i--){
            int t=i+1;
            //不断向右寻找
            while(t<heights.size() && heights[t]>=heights[i]) t=rightheight[t];
            rightheight[i]=t;
        }   
        for(int i=0;i<heights.size();i++){
            int w=rightheight[i]-leftheight[i]-1;
            int h=heights[i];
            int s=h*w;
            sum=max(s,sum);
        }
        return sum;
    }
};

单调栈（按行，横向）

本题是找每个柱子左右两边第一个小于该柱子的柱子，所以使用单调递减栈，只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

栈顶和栈顶的下一个元素以及要入栈的三个元素组成了最大面积的高度和宽度，

分析清楚如下三种情况：

• 情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
• 情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
• 情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

！！！height数组首尾都要加0！！！

伪代码

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result=0;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        stack<int> st;
        st.push(0);
        for(int i=1;i<heights.size();i++){
            if(heights[i]>heights[st.top()]) st.push(i);
            else if(heights[i]==heights[st.top()]){
                st.pop();
                st.push(i);
            }
            else {
                while(!st.empty()&&heights[i]<heights[st.top()]){
                    int mid=st.top();
                    st.pop();
                    int left=st.top();
                    int right=i;
                    int h=heights[mid];
                    int w=right-left-1;
                    int s=h*w;
                    result=max(result,s);
                }
                st.push(i);
            }
        }
        return result;
    }
};

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result=0;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        stack<int> st;
        for(int i=0;i<heights.size();i++){
            while(!st.empty()&&heights[i]<heights[st.top()]){
                int mid=st.top();
                st.pop();
                int left=st.top();
                int right=i;
                int h=heights[mid];
                int w=right-left-1;
                int s=h*w;
                result=max(result,s);
            }
            st.push(i);
        }
        return result;
    }
};