073柱状图中最大的矩形

柱状图中最大的矩形题目链接https://leetcode.cn/problems/largest-rectangle-in-histogram/?envTypestudy-plan-v2envIdtop-100-liked我的解答//方法单调栈 //时间复杂度O(n) //空间复杂度O(n) public int largestRectangleArea(int[] heights) { int ans 0; int n heights.length; DequeInteger stack new LinkedList();//栈中存放下标从栈底到栈顶的下标对应的高度递增 int ptr 0; while(ptr n || !stack.isEmpty()){ if(ptr n (stack.isEmpty() || heights[ptr] heights[stack.peek()])){ stack.push(ptr); ptr; } else{ //收集当前栈顶元素的最大贡献度 int top stack.pop(); int pre stack.isEmpty() ? -1 : stack.peek(); int devote heights[top] * (ptr - pre - 1); //更新答案 ans Math.max(ans, devote); } } return ans; }分析代码的时间复杂度为O(n)空间复杂度为O(n)。解题思路采用单调栈。栈中存放下标从栈底到栈顶的下标对应的高度递增。遍历heights若当前位置的高度大于或等于栈顶下标对应的高度直接将当前位置入栈若当前位置的高度小于栈顶下标对应的高度就从栈中弹出一个下标并统计此下标对应位置的最大贡献度从弹出下标往左找到第一个比它对应高度小的位置也就是弹出它后的栈顶假设为left再从弹出下标往右找到第一个比它对应高度小的位置也就是当前位置假设为ptr那么当前位置的最大贡献度就为当前位置的高度与ptr-left-1的乘积然后更新答案。重复以上操作直到遍历完heights数组的所有元素并且栈为空即可得出最后的答案。看了官方题解后的解答//方法二单调栈 常数优化 //时间复杂度O(n) //空间复杂度O(n) public int largestRectangleArea(int[] heights) { int n heights.length; int[] left new int[n]; int[] right new int[n]; Arrays.fill(right, n); DequeInteger stack new LinkedList();//栈中存放下标从栈底到栈顶的下标对应的高度递增 for(int i0; in; i){ while(!stack.isEmpty() heights[i] heights[stack.peek()]){ right[stack.peek()] i; stack.pop(); } left[i] stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } int ans 0; for(int i0; in; i){ ans Math.max(ans, heights[i] * (right[i] - left[i] - 1)); } return ans; }分析​ 1、官方的解题思路与我的解题思路大体一致但是官方用数组将统计出的每个位置左边第一个高度更小的位置和每个位置右边第一个高度更小的位置存储起来最后根据两个数组来统计答案。而我的解答在弹出栈中元素时直接计算答案逻辑上更难理解在讲述思路时容易显得逻辑不清晰官方的编码分步骤进行在面试时更容易阐述思路。总结本题主要需要分析出题目的类型根据“从每个位置向左和向右扩展到的最远位置统计包含当前位置时所能构成的最大矩阵”将题目转化为了“寻找每个位置往左和往右第一个高度小于当前位置的两个位置”根据这个我们就很容易想到单调栈。