个人网站需要备案,做app公司,wordpress 问答 主题 knowhow,陕西建设 节水 官方网站代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形 文章链接#xff1a;柱状图中最大的矩形 视频链接#xff1a;柱状图中最大的矩形 1. LeetCode 84. 柱状图中最大的矩形
1.1 思路
本题是给一个数组形象得画出图后求矩形的最大面积是多少。本题和42. 接雨水…代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形 文章链接柱状图中最大的矩形 视频链接柱状图中最大的矩形 1. LeetCode 84. 柱状图中最大的矩形
1.1 思路
本题是给一个数组形象得画出图后求矩形的最大面积是多少。本题和42. 接雨水是有点呼应的接雨水是求外面形成最大的接水面积本题是求柱子的内部最大面积。以 [2,1,5,6,2,3] 以 1 高度为基准的柱子左边找比其矮没找到右边找比其矮也没找到那这个 1 的高度就可以贯穿整个数组因此底为数组长度 6面积则为 6*1 等于 6。那再以 5 为基准左边找到第一个比其矮的 1因此无法向左扩展右边找到第一个比其矮的 2因此只能向右扩展到 6因此高为 5宽为 2面积为 10。即以每个柱子为基准向左右找第一个比其矮的柱子然后就可以确定他们的宽高就是这个柱子的高度每个柱子都算一次最后得到最大的即可。单调栈本题就是求左边和右边第一个比当前元素小的。因此单调栈从栈顶到栈底应该是递减的。本题和42. 接雨水也是一样都是确定三个元素当前的基准柱子、左边第一个比当前小的、右边第一个比当前小的。当当前元素比栈顶小的时候就是收获结果的时候栈顶元素就是 middle左边第一个小的元素 left 就是栈顶下一个元素右边第一个小的元素 right 就是当前元素。高 h 就是 heights[middle]宽 wright-left-1面积就是 h*w。数组首尾加 0在本题的数组的头尾各加一个 0为什么因为本题用的是单调递减栈首先要是数组出现 [2,4,6,8] 这种情况那放入栈的时候就是 8,6,4,2 这样的顺序右边是栈底左边是栈顶那这样的话一直都没有走到计算结果的步骤因为一直都没有遍历到当前元素比栈顶元素小的情况那就无法计算结果因此末尾要加 0这样才能触发计算结果的过程。然后要是数组出现 [8,6,4,2] 这种情况那放入栈的时候先是 8 然后当前元素是 6此时就触发计算结果的过程了但是我们计算结果需要 3 个元素这里少了个左边第一个小的元素 left而我们代码中为了避免对空栈操作这一步骤就跳过了然后 8 出栈6 入栈后面依然是这种情况又无法计算结果因此头部要加 0。代码实现定义 result 记录最大的结果。定义栈然后在数组收尾各自插入 0然后将 0 下标入栈。forint i1iheights.lengthi从 1 开始是因为 0 下标已经存入。当前元素大于等于栈顶元素时就直接 stack.push(i)等于的情况直接入栈或者将栈顶弹出再入栈都行只是多了个结果为 0 的操作步骤。如果小于就 while!stack.empty()heights[i]heights[stack.peek()先选取基准柱子middlestack.pop()为什么直接弹出而不是 peek因为我们要求 left这个在栈顶下一个元素。然后接着 if!stack.empty()leftstack.peek()righti高 hheights[middle]宽 wright-left-1。resultMath.maxresulth*w。然后 while 循环结束就要 stack.push(i)。最终 return result 就行。
1.2 代码
class Solution {int largestRectangleArea(int[] heights) {StackInteger st new StackInteger();// 数组扩容在头和尾各加入一个元素int [] newHeights new int[heights.length 2];newHeights[0] 0;newHeights[newHeights.length - 1] 0;for (int index 0; index heights.length; index){newHeights[index 1] heights[index];}heights newHeights;st.push(0);int result 0;// 第一个元素已经入栈从下标1开始for (int i 1; i heights.length; i) {// 注意heights[i] 是和heights[st.top()] 比较 st.top()是下标if (heights[i] heights[st.peek()]) {st.push(i);} else if (heights[i] heights[st.peek()]) {st.pop(); // 这个可以加可以不加效果一样思路不同st.push(i);} else {while (heights[i] heights[st.peek()]) { // 注意是whileint mid st.peek();st.pop();int left st.peek();int right i;int w right - left - 1;int h heights[mid];result Math.max(result, w * h);}st.push(i);}}return result;}
}
