当前位置：首页 > news >正文

073柱状图中最大的矩形

news 2026/5/31 13:57:46

柱状图中最大的矩形

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/?envType=study-plan-v2&envId=top-100-liked

我的解答：

//方法：单调栈 //时间复杂度：O(n) //空间复杂度：O(n) public int largestRectangleArea(int[] heights) { int ans = 0; int n = heights.length; Deque<Integer> 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); Deque<Integer> stack = new LinkedList<>();//栈中存放下标，从栈底到栈顶的下标对应的高度递增 for(int i=0; i<n; 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 i=0; i<n; i++){ ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1)); } return ans; }

分析：

1、官方的解题思路与我的解题思路大体一致，但是官方用数组将统计出的每个位置左边第一个高度更小的位置和每个位置右边第一个高度更小的位置存储起来，最后根据两个数组来统计答案。而我的解答在弹出栈中元素时直接计算答案，逻辑上更难理解，在讲述思路时容易显得逻辑不清晰，官方的编码分步骤进行，在面试时更容易阐述思路。