奉节网站建设,做外贸一般用哪些网站好,做设计的有什么网站,房屋设计软件app自己设计画图84.柱状图中最大的矩形 题目链接#xff1a;84. 柱状图中最大的矩形 本题与接雨水相近。按列来看#xff0c;是要找到每一个柱子左右第一个比它矮的柱子#xff0c;即对于该柱子来说所能组成的最大面积#xff0c;将每个柱子所能得到的最大面积进行对比最终得到最大矩形。 … 84.柱状图中最大的矩形 题目链接84. 柱状图中最大的矩形 本题与接雨水相近。按列来看是要找到每一个柱子左右第一个比它矮的柱子即对于该柱子来说所能组成的最大面积将每个柱子所能得到的最大面积进行对比最终得到最大矩形。 双指针法 class Solution {
public:int largestRectangleArea(vectorint heights) {int ans 0;int size heights.size();vectorint left_low(size);vectorint right_low(size);left_low[0] -1;for(int i 1; i size; i){int idx i - 1;while(idx 0 heights[idx] heights[i]) idx left_low[idx];left_low[i] idx;}right_low[size - 1] size;for(int i size - 2; i 0; --i){int idx i 1;while(idx size heights[idx] heights[i]) idx right_low[idx];right_low[i] idx;}for(int i 0 ; i size; i){int w right_low[i] - left_low[i] - 1;int s w * heights[i];ans max(ans, s);}return ans;}
}; 单调栈法 class Solution {
public:int largestRectangleArea(vectorint heights) {int ans 0;stackint st;st.push(0);for(int i 1; i heights.size(); i){while(!st.empty() (i heights.size() || heights[i] heights[st.top()])){int idx st.top(); st.pop();int w i;if(!st.empty()) w - st.top() 1;int s w * heights[idx];ans max(ans, s);}st.push(i);}return ans;}
};
