衢州网站推广/上海职业技能培训机构一览表
题目描述
给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积
上图是每条宽度为1, 高度 =[2,1,5,6,2,3].的直方图
图中的阴影部分是该直方图中面积最大的矩形，面积为10个单位
例如：
给出的高度 =[2,1,5,6,2,3],
返回10.
基本思路：
常规的思路为 N平方级别，即暴力搜索法
贪心思路：对于一个给定的高度 height 从其左右两边不断延伸（延伸的条件为两边的值比当前的大）
这样确保一个乘数 minHeight 不会减小
栈思路：
每当遇到一个新高度，查看是否比栈顶的大，如果更大，那么入栈（确保栈中为升序）
如果，比栈顶的更小，那么不断退栈，直到比栈顶的小，在退栈过程中，计算每个高度对应矩形的面积
由于栈为升序，所以每退到一个高度时，该高度比之前退出栈的元素小，因为直接 count*height_now
退光所有比当前元素大的元素后，相应的压入同等数量的当前元素（短板效应） 最后存入当前元素
int largestRectangleArea(vector<int>& height){stack<int> h_stack;int size=height.size();if(size==0)return 0;//开始遍历每一个高度int res=0;for(int i=0;i<size;i++){//如果新来的元素 更高，那么入队列因为不会降低之前的高度if(h_stack.empty() || height[i]>=h_stack.top())h_stack.push(height[i]);else //如果更低 那么退栈直到比当前的值小 {int count=0;while(!h_stack.empty() && height[i]<h_stack.top()){count++;//计算退栈途中 块的最大矩形，//由于栈中始终保持升序 那么高度始终为topres=max(res,count*h_stack.top());h_stack.pop();}//退出去的元素采用当前的值填充 因为当前的值更小while(count){h_stack.push(height[i]);count--;}h_stack.push(height[i]);//最后自身入栈//仍然保持栈中 为 升序}}//循环结束 栈中仍然有元素（如一直升序）int count=0;while(!h_stack.empty()){count++;//计算退栈途中 块的最大矩形，//由于栈中始终保持升序 那么高度始终为topres=max(res,count*h_stack.top());h_stack.pop();}return res;}