购物网站html模板,高校网站建设策划,北京品牌网站建设公司,wordpress修改注册表二刷终于能过了.
思路解析:
不愧是hard,第一步就很难想, 对于每一个矩阵,我们要想清楚怎么拿到最大矩阵, 对于每个height[i],我们需要找到left和right,left是i左边第一个小于height[i]的,right是右边第一个小于height[i]的,那么他的最大矩阵就是height[i] * (right-left-…
二刷终于能过了.
思路解析:
不愧是hard,第一步就很难想, 对于每一个矩阵,我们要想清楚怎么拿到最大矩阵, 对于每个height[i],我们需要找到left和right,left是i左边第一个小于height[i]的,right是右边第一个小于height[i]的,那么他的最大矩阵就是height[i] * (right-left-1), 遍历所有的i即可
但是对于1e5我们不可能用O(n^2),所有我们使用单调队列来优化这个取 left,right 的过程.具体说来就是 把right数组设置初值len-1, 从左往右遍历, 如果当前元素小于队尾,就把队尾元素弹出,队尾元素对应的right就是当前的i ,直到队列为空,或者队尾元素大于等于当前元素,遍历结束还存在队列里面的元素的right是len-1 left同理 即是, 把left数组设置初值0, 从右往左遍历, 如果当前元素小于队尾,就把队尾元素弹出,队尾元素对应的left就是当前的i, 直到队列为空,或者队尾元素大于等于当前元素,遍历结束还存在队列里面的元素的right是0 具体代码如下:
class Solution {
public://找左右两边比他大的连续的int largestRectangleArea(vectorint heights){stackint stk;int lenheights.size();vectorint l(len,0),r(len,len-1);for(int i0;iheights.size();i){while(stk.size() heights[i]heights[stk.top()]){ //正常的应该是 的时候pop但是我们这个不是要保证单调,而是要求出左右边界,所以我们使用的时候popr[stk.top()]i-1; //所以离开的时候,就是可以判断 剩下没有被赶走的就是len-1了stk.pop(); }stk.push(i);}stackint stk1; //清空一个栈,不如新建一个for(int ilen-1;i0;i--){while(stk1.size() heights[i]heights[stk1.top()]){l[stk1.top()]i1; //所以离开的时候,就是可以判断 剩下没有被赶走的就是0了stk1.pop();}stk1.push(i);} int ans0;for(int i0;ilen;i){ansmax(ans,(r[i]-l[i]1)*heights[i]);}return ans;}
};//给两个测试用例
//[2,1,5,6,2,3,2]
//[2,1,5,6,2,3,3,3,2]
