代码随想录算法训练营第六十天|84.柱状图中最大的矩形
代码随想录算法训练营第六十天|84.柱状图中最大的矩形
柱状图中最大的矩形
84.柱状图中最大的矩形
文章讲解：https://programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html
题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/
视频讲解：https://www.bilibili.com/video/BV1Ns4y1o7uB/
自己看到题目的第一想法
没太多想法，快速看答案熟悉题目。
看完代码随想录之后的想法
和接雨水类似，整个处理逻辑就是遍历每一列，选取该列然后求该列的面积值。
使用单调栈来存储index，和接雨水从栈顶到栈底递增不一样。该单调栈从栈顶到栈底递减，该单调栈栈顶是最大的，遇到比他小的，就将当前元素pop，用left、middle求出最大值。int w = right - left - 1;(宽度，right和left那一列的都不要)int h = heights[mid];result = max(result, w * h);这里没理解为什么只求左右两边left和right就可以了，会不会出现往前延伸更大的值？？（这里不会，核心是要理解当到i时，高度只能用i位置的高度）
求柱子左边第一个比他矮的，右边第一个比他矮的，这样就能找到这个柱子的宽，然后再乘以这个柱子的高，求得得就是当前柱子的面积。
主要就是分析清楚如下三种情况：
情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
为什么前后还需要再增加一个0呢？ 这是因为防止整个数组就是单调的情况。
结尾加0:如果数组本身就是升序的，例如[2,4,6,8]，那么入栈之后 都是单调递减，一直都没有走 情况三 计算结果的哪一步，所以最后输出的就是0了。那么结尾加一个0，就会让栈里的所有元素，走到情况三的逻辑。
开头加0:如果数组本身是降序的，例如 [8,6,4,2]，在8入栈后,6开始与8 进行比较，此时我们得到 mid(8)，right（6），但是得不到left。因为将8弹出之后，栈里没有元素了，那么为了避免空栈取值，直接跳过了计算结果的逻辑。之后又将6 加入栈（此时8已经弹出了），然后就是4与栈口元素8进行比较，周而复始，那么计算的最后结果resutl就是0。
自己实现过程中遇到哪些困难
自己实现的代码：自己的代码整体思路是对的，但是在newArr[i] < newArr[st.peek()]情况下时往stack里push的位置写错了，不应该写在循环内，而应该写在循环外面，因为不管处理结果怎么样都需要把当前值往堆栈里塞。
public int largestRectangleArea(int[] heights) {
Stack<Integer> st = new Stack<Integer>();
int[] newArr = new int[heights.length + 2];
newArr[0] = 0;
newArr[newArr.length - 1] = 0;
System.arraycopy(heights, 0, newArr, 1, heights.length);
System.out.println(Arrays.toString(newArr));
st.push(0);
int result = 0;
for(int i = 1; i < newArr.length; i++){
// 三种情况。大于、小于、等于
if(newArr[i] > newArr[st.peek()]){
st.push(i);
}else if(newArr[i] == newArr[st.peek()]){
st.pop();
st.push(i);
}else{
while(!st.isEmpty() && newArr[i] < newArr[st.peek()]){
int mid = st.peek();
st.pop();
if(!st.isEmpty()){
int left = st.peek();
int w = i - left - 1;
int h = newArr[mid];
result = Math.max(w * h,result);
}
// 这里写错了应该写在下面
st.push(i);
}
// st.push(i); 这个应该写在这里。
}
}
return result;
}
今日收获&学习时长
加深了对单调栈的运用，单调栈的核心就是比较值大小的时候可以使用。60天的课花了将近4个月，完结撒花，开始二刷！
原文地址：https://blog.csdn.net/shanshe7934/article/details/135985893
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！