帝国做网站是选择静态还是伪静态,网站地图生成软件,建设网站有哪些公司,网站内容优化细节柱状图中最大的矩形 类似接雨水#xff08;反过来#xff0c;相当于找接雨水最少的一段#xff09;题解1 暴力搜索#xff08;超时#xff09; O ( N 2 ) O(N^2) O(N2)另一种 题解2 单调栈【重点学习】常数优化 给定
n 个非负整数#xff0c;用来表示柱状图中各个柱子的… 柱状图中最大的矩形 类似接雨水反过来相当于找接雨水最少的一段题解1 暴力搜索超时 O ( N 2 ) O(N^2) O(N2)另一种 题解2 单调栈【重点学习】常数优化 给定
n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。 求在该柱状图中能够勾勒出来的矩形的最大面积。 提示
1 heights.length 1 0 5 10^5 1050 heights[i] 1 0 4 10^4 104
类似接雨水反过来相当于找接雨水最少的一段
题解1 暴力搜索超时 O ( N 2 ) O(N^2) O(N2)
class Solution {
public:int largestRectangleArea(vectorint heights) {int s heights.size();int maxs 0;for(int l 0; l s; l){int minL INT_MAX;for(int r l; r s; r){minL min(minL, heights[r]);maxs max(maxs, minL*(r-l1));}}return maxs;}
};另一种
class Solution {
public:int largestRectangleArea(vectorint heights) {int s heights.size();int maxs 0;for(int i 0; i s; i){int l i;int r i;int tmph heights[i];while(l 1 heights[l-1] tmph)--l;while(r 1 s heights[r1] tmph)r;maxs max(maxs, (r-l1)*tmph);}return maxs;}
};题解2 单调栈【重点学习】
class Solution {
public:int largestRectangleArea(vectorint heights) {int s heights.size();stackint stk; // 单调栈下标对应值保持非严格递增vectorint l(s, -1), r(s, s);int maxs 0;// 从左向右// 找到离i最近的 hegihts[i]的左边界for(int i 0; i s; i){while(stk.size() heights[stk.top()] heights[i])stk.pop();l[i] (stk.empty() ? -1 : stk.top());stk.push(i);}stk stackint();// 从右向左// 找到离i最近的 hegihts[i]的右边界for(int i s-1; i 0; i--){while(stk.size() heights[stk.top()] heights[i])stk.pop();r[i] (stk.empty() ? s : stk.top());stk.push(i);}for(int i 0; i s; i){// 使用单调栈的初衷 以height[i]为高度的矩形对应的宽 r[i]-l[i]maxs max(maxs, heights[i]*(r[i]-l[i]-1));}return maxs;}
};常数优化
class Solution {
public:int largestRectangleArea(vectorint heights) {int s heights.size();stackint stk; // 单调栈下标对应值保持非严格递增vectorint l(s, -1), r(s, s);int maxs 0;// 从左向右for(int i 0; i s; i){while(stk.size() heights[stk.top()] heights[i]){r[stk.top()] i;stk.pop();}l[i] (stk.empty() ? -1 : stk.top());stk.push(i);}for(int i 0; i s; i){maxs max(maxs, heights[i]*(r[i]-l[i]-1));}return maxs;}
};
