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

LeetCode 84. 柱状图中最大的矩形

news 来源：原创 2024/5/9 22:29:57

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]

输出：10

解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]

输出： 4

提示：

1 <= heights.length <=10^5
0 <= heights[i] <= 10^4

解法思路（参考官方题解及视频讲解）:

1、暴力1 O(n^3)
for i -> 0, nfor j -> i, n(i, j) -> 最小高度，areaupdate max-area
2、暴力2 O(n^2)
for i -> 0, n:找到 left bound, right boundarea = height[i] * (right - left)update max-area
3、Stack

4、优化 Stack，加哨兵元素

法一（超时）：

class Solution {public int largestRectangleArea(int[] heights) {// Time: O(n^3)// Space: O(1)int maxArea = 0;for (int i = 0; i < heights.length; i++) {for (int j = i; j < heights.length; j++) {int minHeight = Integer.MAX_VALUE;for (int k = i; k <= j; k++) {minHeight = Math.min(minHeight, heights[k]);}maxArea = Math.max(maxArea, minHeight * (j - i + 1));}}return maxArea;}
}

法二（超时）：

class Solution {public int largestRectangleArea(int[] heights) {// Time: O(n^2)// Space: O(1)int maxArea = 0;for (int i = 0; i < heights.length; i++) {int minHeight = Integer.MAX_VALUE;for (int j = i; j < heights.length; j++) {minHeight = Math.min(minHeight, heights[j]);maxArea = Math.max(maxArea, minHeight * (j - i + 1));}}return maxArea;}
}

法三：

class Solution {public int largestRectangleArea(int[] heights) {// Stack 空间换时间// 特殊情况1：遍历完成后，栈内元素出栈时一定可以扩展到数组的末尾// 特殊情况2：弹出栈顶后栈为空，一定可以扩散到数组最左边// 特殊情况3：栈中存在高度相等的元素，出栈// Time: O(n)// Space: O(n)int len = heights.length;if (len == 0) return 0;if (len == 1) return heights[0];int maxArea = 0;Deque<Integer> stack = new ArrayDeque<>();for (int i = 0; i < len; i++) {// 当前元素的高度严格小于栈顶元素的高度时，出栈while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {int height = heights[stack.removeLast()];// 特殊情况3：栈中存在高度相等的元素，出栈while (!stack.isEmpty() && heights[stack.peekLast()] == height) {stack.removeLast();}// 特殊情况2：弹出栈顶后栈为空，一定可以扩散到数组最左边int width = stack.isEmpty() ? i : (i - stack.peekLast() - 1);maxArea = Math.max(maxArea, width * height);}stack.addLast(i);}// 弹出栈中所有元素while (!stack.isEmpty()) {int height = heights[stack.removeLast()];while (!stack.isEmpty() && heights[stack.peekLast()] == height) {stack.removeLast();}// 特殊情况1：遍历完成后，栈内元素出栈时一定可以扩展到数组的末尾int width = stack.isEmpty() ? len : (len - stack.peekLast() - 1);maxArea = Math.max(maxArea, width * height);}return maxArea;}
}

优化法三：

class Solution {public int largestRectangleArea(int[] heights) {// Stack(add Sentinel)// Time: O(N)// Space: O(N)int len = heights.length;if (len == 0) return 0;if (len == 1) return heights[0];int maxArea = 0;int[] newHeights = new int[len + 2];for (int i = 0; i < len; i++) {newHeights[i + 1] = heights[i];}len += 2;heights = newHeights;Deque<Integer> stack = new ArrayDeque<Integer>();stack.addLast(0);for (int i = 1; i < len; i++) {while (heights[stack.peekLast()] > heights[i]) {int height = heights[stack.removeLast()];int width = i - stack.peekLast() - 1;maxArea = Math.max(maxArea, width * height);}stack.addLast(i);}return maxArea;}
}