前言
今天代码随想录一刷也告一段落了,没想到我居然坚持下来了,一节都没有落下,学习到了很多种不同的解题思路,也和大家一块交流了很多,哈哈也许不久以后我还得再次二刷代码随想录,希望这一系列的题解能给大家带来帮助,如想要系统学习,请参照代码随想录网站的题解以及b站的配套视频
这里给大家放上直达链接
LeetCode T84 柱状图的最大矩形
题目链接:84. 柱状图中最大的矩形 - 力扣（LeetCode）
题目思路:
废话不多说,最后一天,打起十二分的精神
这题其实和上一题的接雨水问题有着异曲同工之妙
这一题其实就是接雨水的反面,接雨水是找凹槽,这里其实是凸起,我们需要找到左右两边比目前遍历元素小的元素,同样的思路,两者作差-1得到宽,高就是中间元素在数组中的值
唯一的难点就是在原数组两边得加上两个0,因为如果这里数组是按照升序排列的,这里我们这个方式就保持了一直递减,没有大于的情况来操作,如果我们在两边加上两个0其实就保证了两边的元素都可以处理到,无论是升序还是降序排列的数组都能够得到很好的处理
升序:保持递减无法处理
降序:一直处理无法达到栈内有两个元素的情况,最后只会是空栈.
题目代码:
class Solution { public int largestRectangleArea(int[] heights) { int result = 0; Stack<Integer> st = new Stack<>(); int[] res = new int[heights.length+2]; res[0] = 0; res[res.length-1] = 0; for(int i = 1;i<heights.length+1;i++){ res[i] = heights[i-1]; } st.push(0); for(int i = 1;i<res.length;i++){ if(res[i]>=res[st.peek()]){ st.push(i); }else{ while(!st.isEmpty() && res[i]<res[st.peek()]){ int tmp = st.peek(); st.pop(); int left = st.peek(); int w = i-left-1; int h = res[tmp]; result = Math.max(result,h*w); } st.push(i); } } return result; } }
