直方图内最大矩形

[编程题]直方图内最大矩形

热度指数：4782 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组heights，长度为n，height[i]是在第i点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少?

1.每个直方图宽度都为1

2.直方图都是相邻的

3.如果不能形成矩形，返回0即可

4.保证返回的结果不会超过2³¹-1

数据范围:

$0 <= heights[i] <= 10^4$

$0 <= heights.length <=10^5$

如输入[3,4,7,8,1,2]，那么如下:

示例1

输入

[3,4,7,8,1,2]

输出

示例2

输入

[1,7,3,2,4,5,8,2,7]

输出

算法知识视频讲解

Java

牛客499848474号

用Deque，时间空间复杂度都是O(n)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param heights int整型一维数组
     * @return int整型
     */
    public int largestRectangleArea (int[] heights) {
        // write code here
        int result = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i <= heights.length; i++) {
            int cur = i == heights.length ? 0 : heights[i];
            while (!stack.isEmpty() && heights[stack.peekFirst()] >= cur) {
                int height = heights[stack.pollFirst()];
                int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
                result = Math.max(result, height * (i - left));
            }
            stack.offerFirst(i);
        }
        return result;
    }
}

发表于 2025-01-01 21:03:08 回复(0)

Java

苏觅云

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int countArea(int[] heights, int N, int i) {
        int le = i, ri = i;
        while(le > -1 && heights[le] >= heights[i]) le--;
        while(ri < N  && heights[ri] >= heights[i]) ri++;
        return (ri - le - 1) * heights[i];
    }
    public int largestRectangleArea (int[] heights) {
        // write code here
        if(heights == null) {
            return 0;
        }
        int N = heights.length;
        if(N == 0) {
            return 0;
        } else if(N == 1) {
            return heights[0];
        }
        int pre = heights[0];
        int maxArea = countArea(heights, N, 0);
        for(int i = 1; i < N; i++) {
            if(heights[i] == pre) {
                continue;
            }
            pre = heights[i];
            int area = countArea(heights, N, i);
            if(area > maxArea) {
                maxArea = area;
            }
        }
        return maxArea;
    }
}

发表于 2022-05-19 16:49:22 回复(1)

Java

pein531

单调栈求解，遍历高度数组，在此过程中维持栈底到栈顶的单调递增，当遍历到某个位置i时：

如果栈为空或heights[i]>heights[stack.peek()]，说明此时能保证单调性，直接把下标i压栈；
否则开始结算面积：先弹出栈顶元素，以heights[stack.pop()]作为高度，而此时i是它右边第一个比它小的高度，说明这个高度的矩形能够往右延展至i，让这个矩形从栈顶（矩形左边界）的位置延展至i，结算面积即可；不断弹栈，直到heights[i]压栈后可以保证栈的单调性，然后把i压栈，在弹栈的过程中不断更新矩形的左边界和矩形面积。

需要注意的是：遍历完数组后栈并不一定为空，所以还需要结算以栈中元素为矩形左边界构成的矩形面积（此时右边界为heights.length）。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int largestRectangleArea (int[] heights) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        for(int i = 0; i < heights.length; i++){
            while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                int h = heights[stack.pop()];
                int L = stack.isEmpty()? 0: stack.peek() + 1;
                maxArea = Math.max(maxArea, (i - L) * h);
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int h = heights[stack.pop()];
            int L = stack.isEmpty()? 0: stack.peek() + 1;
            maxArea = Math.max(maxArea, (heights.length - L) * h);
        }
        return maxArea;
    }
}

可能有些新手会有这样的疑问：为什么单调栈求解题目的时候都是把下标压入栈中，而不是直接压数组元素？这是因为，题目给你的数组已经摊在这了，只要有下标，一定可以定位到某个高度。而如果你压入的是高度，在结算矩形面积的时候就难以确定矩形的底边是从哪到哪，因此压入下标所维持的信息是更多的。

编辑于 2021-12-23 11:44:32 回复(0)