代码随想录算法训练营第六十天 | 单调栈柱状图中最大的矩形完结撒花

本文主要是介绍代码随想录算法训练营第六十天 | 单调栈柱状图中最大的矩形完结撒花，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

柱状图中最大的矩形

双指针解法
本题要记录记录每个柱子左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。
在寻找的过程中使用了while

class Solution {public int largestRectangleArea(int[] heights) {int[] minLeftIndex = new int[heights.length];int[] minRightIndex = new int[heights.length];int length = heights.length;// 记录每个柱子，左边第一个小于该柱子的下标minLeftIndex[0] = -1; for (int i = 1; i < length; i++) {int t = i - 1;while (t >= 0 && heights[t] >= heights[i]) {t = minLeftIndex[t];}minLeftIndex[i] = t;}// 记录每个柱子 右边第一个小于该柱子的坐标minRightIndex[length - 1] = length;  // 注意这里初始化，防止下面while死循环for (int i = length - 2; i >= 0; i--) {int t = i + 1;while (t < length && heights[t] >= heights[i]) {t = minRightIndex[t];}minRightIndex[i] = t;}// 求和int result = 0;for (int i = 0; i < length; i++) {int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);result = Math.max(sum, result);}return result;}
}

单调栈

在这里插入图片描述

栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

class Solution {public int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<>();// 数组扩容，在头尾各加入一个元素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;for (int i = 1; i < heights.length; i++) {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()]) {int 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;}
}