算法刷题记录 Day52

Date: 2024.04.20

lc 84. 柱状图中最大的矩形

// 单调栈
class Solution {
public:int largestRectangleArea(vector<int>& heights) {// 对于每个柱子，我们考虑按当前柱子进行中心扩散，直到找到其左侧及其右侧，高度小于该柱子的柱子为止。// 例如当前柱子高度为2，则所有高度大于等于2的柱子都可以加入该柱子为高的矩形。// 因此，我们需要找到左侧和右侧第一个高度小于指定高度的柱子。（则范围内均为大于等于该高度的柱子）int n = heights.size();vector<int> leftIdx(n, 0);vector<int> rightIdx(n, 0);// 我们借助单调栈获取左右第一个高度小于指定高度的数。// 要获取左侧最近较小值，我们维护一个单调递增的栈。每当一个元素要入栈，我们舍去栈顶的大于该元素的值。// 若栈不为空，则此时的栈顶，即为该元素的左侧第一个更小值。若栈为空，则左侧第一个更小值视作0.stack<int> st;for(int i=0; i<n; i++){int cur_height = heights[i];if(!st.empty() && cur_height > heights[st.top()]){leftIdx[i] = st.top();}else if(!st.empty() && cur_height <= heights[st.top()]){while(!st.empty() && cur_height <= heights[st.top()]){st.pop();}if(st.empty()){leftIdx[i] = -1;}else{leftIdx[i] = st.top();}}else if(st.empty()){leftIdx[i] = -1;}st.push(i);}while(!st.empty()){st.pop();}for(int i=n-1; i>=0; i--){int cur_height = heights[i];if(!st.empty() && cur_height > heights[st.top()]){rightIdx[i] = st.top();}else if(!st.empty() && cur_height <= heights[st.top()]){while(!st.empty() && cur_height <= heights[st.top()]){st.pop();}if(st.empty()){rightIdx[i] = n;}else{rightIdx[i] = st.top();}}else if(st.empty()){rightIdx[i] = n;}st.push(i);}int max_area = -1;for(int i=0; i<n; i++){// cout<<"i:"<<i<<", leftIdx:"<<leftIdx[i]<<", rightIdx:"<<rightIdx[i]<<", (r-l-1):"<<(rightIdx[i] - leftIdx[i] - 2)<<", h:"<<heights[i]<<endl;int cur_area = (rightIdx[i] - leftIdx[i] - 1) * heights[i];max_area = max(max_area, cur_area);}return max_area;}
};// 暴力， ON^2， 超时
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int max_area = INT_MIN;int n = heights.size();// 遍历起点和终点，矩形高为所有点中min，宽为（终点-起点+1）;for(int start = 0; start < n; start++){int cur_min = heights[start];for(int end = start; end < n; end++){cur_min = min(cur_min, heights[end]);int cur_area = (end - start + 1) * cur_min;max_area = max(max_area, cur_area);}}return max_area;}
};