代码随想录算法训练营第60天|84.柱状图中最大的矩形

2023-12-23 22:04:10

JAVA代码编写

84. 柱状图中最大的矩形

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

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

示例 1:

img

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

示例 2:

img

输入: heights = [2,4]
输出: 4

提示:

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104

教程:https://programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html

方法一:暴力解法

思路:两个for循环,第一个循环i控制heights的起始位置,第二个循环i控制heights的结束位置,每次记录i-j的矩形面积,去最大的直到遍历结束。

力扣上没法通过

复杂度分析

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度: O ( 1 ) O(1) O(1)
public class Solution {
    public static int getMaxRectangleArea(int[] heights) {
        int maxArea = 0;
        int length = heights.length;

        for (int i = 0; i < length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                int width = j - i + 1;
                int area = minHeight * width;
                maxArea = Math.max(maxArea, area);
            }
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        int maxArea = getMaxRectangleArea(heights);
        System.out.println("最大矩形面积:" + maxArea);
    }
}

方法二:左右指针

思路:遍历下标i,找到左边小于等于当前高度,找到右边小于等于当前高度,这样宽度就是右指针-左指针+1,高度就是hegihts[i],从而计算面积,每次记录最大的面积。

复杂度分析

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
    public int largestRectangleArea(int[] heights) {
        
        int maxArea = 0;
        int length = heights.length;

        for (int i = 0; i < length; i++) {
            int left = i;
            int right = i;

            // 找到左边第一个小于 heights[i] 的位置
            while (left > 0 && heights[left - 1] >= heights[i]) {
                left--;
            }

            // 找到右边第一个小于 heights[i] 的位置
            while (right < length - 1 && heights[right + 1] >= heights[i]) {
                right++;
            }

            int width = right - left + 1;
            int area = heights[i] * width;
            maxArea = Math.max(maxArea, area);
        }

        return maxArea;
    }
}

方法三:单调栈

思路

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
import java.util.Stack;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] newHeight = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeight, 1, heights.length); // 将原数组heights从下标0 开始复制到 新数组newHeight的下标1位置
        newHeight[heights.length+1] = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        int res = 0;
        for (int i = 1; i < newHeight.length; i++) {
            while (newHeight[i] < newHeight[stack.peek()]) {
                int mid = stack.pop();
                int w = i - stack.peek() - 1;
                int h = newHeight[mid];
                res = Math.max(res, w * h);
            }
            stack.push(i);

        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.largestRectangleArea(new int[]{2,1,5,6,2,3});
    }
}

文章来源:https://blog.csdn.net/Catherinemin/article/details/135174153
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。