网站开发属于技术合同,创建网站投资多少,浙江住建局官方网站,免费商标图案设计大全单调栈#xff0c;又一次经典来袭#xff01; LeetCode#xff1a;84.柱状图中最大的矩形_哔哩哔哩_bilibili 首先补充昨天接雨水题目解法的更新#xff0c;代码随想录 中给出双指针和单调栈的解法#xff0c;其中所采用的思想是计算每一列可以容纳的雨水#xff0c;非常… 单调栈又一次经典来袭 LeetCode84.柱状图中最大的矩形_哔哩哔哩_bilibili 首先补充昨天接雨水题目解法的更新代码随想录 中给出双指针和单调栈的解法其中所采用的思想是计算每一列可以容纳的雨水非常的关键是指导双指针的重要思想。双指针的核心思路是对于每一列其所容纳的雨水量必定取决于左右两
侧的最高高度即每一列考虑自身是出于山谷的中间还是两边这是所有可以容纳雨水的情况山峰的情况是必定容纳不了雨水的。
而双指针的优化是使用了数组存储各个位置所记录的单边最大高度有一点动态规划的思想。双指针的求解思路非常的厉害单调栈也是延续这一个思想栈内以递增的顺序进行元素的存储。其中出现大于栈顶的元素height[i]再结合栈内一定是栈顶往下递增的所以此时出现了山谷那么需要仍然按照列可容纳的思路进行雨水量的累加。
// 减去height[mid]就是所谓的减去高度差的思想
int h Math.min(height[left], height[index]) - height[mid];
// 计算间隔
int w index - left - 1;
// 计算剔除了高度差后目前出栈列与当前i之间可以填入的雨水量
int hold h * w;
if (hold 0) sum hold;stackTop stack.peek();
// 双指针解法真的太厉害了我个人觉得比单调栈来的神class Solution {public int trap(int[] height) {int length height.length;if (length 2) return 0;int[] maxLeft new int[length];int[] maxRight new int[length];// 记录每个柱子左边柱子最大高度maxLeft[0] height[0];for (int i 1; i length; i) maxLeft[i] Math.max(height[i], maxLeft[i-1]);// 记录每个柱子右边柱子最大高度maxRight[length - 1] height[length - 1];for(int i length - 2; i 0; i--) maxRight[i] Math.max(height[i], maxRight[i1]);// 求和int sum 0;for (int i 0; i length; i) {int count Math.min(maxLeft[i], maxRight[i]) - height[i];if (count 0) sum count;}return sum;}
}
84. 柱状图中最大的矩形
思路单调栈顺序是递减每一次出栈都将计算当前出栈高度与左右比自己更高的高度所形成矩形面积。通过本题我们可以得出进栈元素是更新结果的一个边界由于单调栈的单调特性因此栈顶的下一个位置的元素是另一个边界即结果可以通过这三者完成计算。此外采用栈顶元素的下一个位置的元素直接参与计算那么自然在当前元素出栈后将会以下一个元素作为栈顶来开展下一此结果更新那么所谓的高度差的概念其实是去栈内每一次计算结果时需要将当前位置的高度与左右两侧边界的高度进行三者的筛选在接雨水题中需要用左右两侧的最小值减去当前位置高度得到当前位置的雨水量。而在矩形中高度差体现在每次更新面积时height[mid]就是当前高度范围内的最小值考虑了与(left,right)之间高度的高度比较即高度差。
class Solution {int largestRectangleArea(int[] heights) {ArrayDequeInteger st new ArrayDeque();// 数组扩容在头和尾各加入一个元素为了有效的应对heights全员递增或全员递减的情况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) {// 栈内排序是递减的遇到更大的元素直接进栈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;// 计算长这一步非常的关键这里剔除了高度更小的left和right加入计算而是去已经left与right之间已经出栈的高的高度加入计算// 如果mid是最高的那么w等于1如果mid不是最高的那么(left,right)之间的元素都比height[mid]来的更大int w right - left - 1;// 当前出栈元素是三个位置内高度最高的以mid为基准进行面积计算int h heights[mid];result Math.max(result, w * h);}st.push(i);}}return result;}
}
