代码随想录算法训练营第六十天 | 84.柱状图中最大的矩形

84.柱状图中最大的矩形

题目链接：84. 柱状图中最大的矩形

本题与接雨水相近。按列来看，是要找到每一个柱子左右第一个比它矮的柱子，即对于该柱子来说所能组成的最大面积，将每个柱子所能得到的最大面积进行对比最终得到最大矩形。

双指针法

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int ans = 0;int size = heights.size();vector<int> left_low(size);vector<int> 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(vector<int>& heights) {int ans = 0;stack<int> 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;}
};