手机上做网站的软件,郑州网页网站制作,yanderedev wordpress,门户网站的自身的特性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;}
};
