【C++编程能力提升】

一、84 柱状图中最大的矩形

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

核心：利用递减栈求解最大矩形的面积，只有从栈顶到栈底保持递减才使得栈顶元素的最大值，那么当前遍历元素小于栈顶元素时就需要计算此时的矩形面积（不太理解？）

    int largestRectangleArea(vector<int>& heights) {
    //当前元素大于栈顶元素直接入栈，当前元素小于栈顶元素时与栈顶元素和栈顶下一个元素构成了矩形
    int res=0; //记录矩形的最大面积
    stack<int> stk; //递减栈，从栈顶到栈底递减
    heights.insert(heights.begin(),0); //数组开头插入元素0
    heights.push_back(0);  //数组末尾插入元素0

    stk.push(0);  //第一个元素下标入栈
    for(int i=1;i<heights.size();++i)
    {
        if(heights[i]>heights[stk.top()])
            stk.push(i); //当前元素大于栈顶元素，则入栈
        else if(heights[i]==heights[stk.top()])
        {//更新栈顶元素，即先弹出栈顶元素再将当前元素下标入栈
            stk.pop();
            stk.push(i);
        }
        else
        {
            while(!stk.empty() && heights[i]<heights[stk.top()])
            {//栈顶元素最大，其左边和右边(当前遍历元素)都是小于栈顶元素的值
                int mid=stk.top(); //此时栈顶元素下标值
                stk.pop(); 
                if(!stk.empty())
                {
                    int left=stk.top();
                    int right=i;
                    int w=right-left-1; //左右边界宽度-1
                    int h=heights[mid];//最大元素值
                    res=max(res,w*h);
                }
            }
            stk.push(i);
        }
    }
    return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37