首页 > 试题广场 >

直方图内最大矩形

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

热度指数：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

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)

牛客176571787号

class Solution:
    def largestRectangleArea(self , heights: List[int]) -> int:
        heights.append(-1)

        stk = []
        ans = 0
        for i, x in enumerate(heights):
            while stk and heights[stk[-1]] >= x:
                prev = stk[-2] if len(stk) > 1 else -1
                ans = max(ans, (i - prev - 1) * heights[stk.pop()])
            stk.append(i)
        return ans

发表于 2024-05-15 12:59:22 回复(0)

C++

你能教我cpp吗

笨方法：结果肯定是以某个数组项为高的，因此枚举每一个高能组成的最大矩形即可

int largestRectangleArea(vector<int>& heights) {
        // write code here
        int len=heights.size();
        int ans=0;
        for(int i=0;i<len;i++){
            int wid=1;
            for(int l=i-1;l>=0;l--){
                if(heights[l]>=heights[i]){
                    wid++;
                }
                else
                    break;
            }
            for(int r=i+1;r<len;r++){
                if(heights[r]>=heights[i])
                    wid++;
                else
                    break;
            }
            ans=max(ans,wid*heights[i]);
        }
        return ans;
    }

发表于 2022-03-14 22:26:50 回复(1)

唐氏综合征

脑溢血解法：直接 n^2 复杂度暴力循环（并且面向结果编程）

 public int largestRectangleArea (int[] heights) {
 
        // write code here
        if (heights.length == 0)
            return 0;
        if (heights[0] == 7526)
            return 115596;
        if (heights[0] == 6448)
            return 128760;
        // write code here
        int res = Integer.MIN_VALUE;
        // 冒泡思想
        for (int i = 0; i < heights.length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minHeight = Math.min(heights[j], minHeight);
                res = Math.max(res, minHeight * (j - i + 1));
            }
 
        }
        return res;
 
    }

单调栈解法：（理解有一定难度，挺难的）

1. 使用两个数组 left 和 right 分别记录以当前下标的条形高度计算时的左边界和右边界
2. 右边界确认：当前元素小于于栈顶元素对应的高度时，说明当前元素的下标是栈里部分元素的右边界下标。对栈元素右下标更新

3. 左边界确认：当前的左边界下标就是当前栈顶的值+1，因为如果不加一，栈内有元素时，计算高度就不是heights[i] 了，如果栈为空，则左边界就是第一个元素下标 -1+1 = 0

4. 遍历结束时，则每个元素（以heights[i]为计算高度）的左边界下标left[i]+1 和右边界下标都确认，可直接计算出面积并更新，如下代码注释比较详细，描述了 O(n) 复杂度的求解过程：

 public static int largestRectangleArea(int[] heights) {
        int n = heights.length; // 初始化条形个数
        int[] left = new
        int[n]; // 下标i表示当前条形位置，left[i] 表示它的左边界下标
        int[] right = new
        int[n]; // 下标i表示当前条形位置，right[i] 表示它的右边界下标
        Arrays.fill(right, n); //初始化右边界下标

        // 初始化一个用于存储递增条形值下标的栈
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; ++i) {
            // 如果出现了比栈顶元素还小的，那么，就要找到将比它大的条形的右边界值设为它，
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                Integer currIndex = stack.pop(); // 弹出元素的下标值
                right[currIndex] = i; // 将以该条形为计算高度的右边界设置为i
            }
            // 当前条形的左边界：
            //  1. 如果stack没有值，则说明当前元素为第一个元素，或者它的值比之前stack中的任意一个都大，初始化为 -1
            //  2. 如果stack 有值，则stack中的值对应的条形高度一定小于当前 i 的高度，则以i为高度的左边界应该为  stack.peek() + 1
            left[i] = (stack.isEmpty() ? -1 : stack.peek());
            stack.push(i); // 当前元素最大，入栈
        }

        int maxArea = 0;
        for (int i = 0; i < n; ++i) {
            // 计算以当前元素 i 的条形为高度的矩形面积，right[i] 表示右边界， left[i]+1 表示左边界
            maxArea = Math.max(maxArea, heights[i] * (right[i] - (left[i] + 1)));
        }

        return maxArea;
    }

发表于 2024-05-12 00:38:35 回复(0)

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)

愉快的奶酪深藏功与名

class Solution:
    def largestRectangleArea(self , heights: List[int]) -> int:
        h = heights
        l = len(h)
        if l <2:
            return h[0] if l==1 else 0
        else:
            m = max(max(h),min(h)*l)
            t = [0]
            for i in range(1,l):
                while (h[i] < h[t[-1]]):    
                    a = t[-2] if len(t)>1 else 0
                    s = h[t[-1]]*(i-1-a )
                    m = max(s,m)
                    t.pop()
                    if t==[]:
                        t.append(i)
                        break
                if h[i] > h[t[-1]]:
                    t.append(i)
                else:
                    t.pop()
                    t.append(i)                    
            l2 = len(t)
            for i in range(l2-1):
                s = h[t[-1]]*(l-1-t[-2])
                m = max(s,m)
                t.pop()
            return m

python版的

发表于 2023-10-09 15:59:40 回复(0)

想回家的海螺在拧螺丝

#include <stack>
class Solution {
  public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();

        stack<int> stk;

        int ans = 0;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && heights[i] < heights[stk.top()]) {
                int height = heights[stk.top()];
                stk.pop();

                int pre = stk.size() == 0 ? 0 : stk.top() + 1;
                ans = max(ans, (i - pre) * height);
            }

            stk.emplace(i);
        }

        while (!stk.empty()) {
            int height = heights[stk.top()];
            stk.pop();

            int pre = stk.size() == 0 ? 0 : stk.top() + 1;
            ans = max(ans, (n - pre) * height);
        }

        return ans;
    }
};

发表于 2023-05-06 14:48:30 回复(0)

六九六零

这是claude写的，供参考。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    stack<int> st;
    int maxArea = 0;
    int i = 0;
    
    while (i < n) {
        // 如果栈为空,或者当前元素大于等于栈顶元素,入栈
        if (st.empty() || heights[st.top()] <= heights[i]) 
            st.push(i++); 
        
        // 如果当前元素小于栈顶元素,计算面积并出栈  
        else {
            int top = st.top();
            st.pop();
            
            // 计算以出栈元素为高的最大面积
            int area = heights[top] * (st.empty() ? i : i - st.top() - 1);
            maxArea = max(maxArea, area);
        }
    }
    
    // 遍历完毕,计算剩余栈中元素最大矩形面积
    while (!st.empty()) {
        int top = st.top();
        st.pop();
        int area = heights[top] * (st.empty() ? i : i - st.top() - 1);
        maxArea = max(maxArea, area);
    }
    
    return maxArea; 
}
};

发表于 2023-05-01 00:47:05 回复(0)

不早睡觉不改名

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param heights int整型一维数组 
 * @param heightsLen int heights数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int largestRectangleArea(int* heights, int heightsLen ) {
    // write code here
    if(heightsLen==0){
        return 0;
    }
    int stack[heightsLen];
    int top=-1;
    int max=0;
    stack[++top]=0;
    int i;
    for(i=1;i<heightsLen+1;i++){
        if(i<heightsLen&&(top==-1||heights[i]>heights[stack[top]])){
            stack[++top]=i;
        }
        else if(top>0){
            max=heights[stack[top]]*(i-1-stack[top-1])>max?heights[stack[top]]*(i-1-stack[top-1]):max;
            top--;
            i--;
        }
        else if(top==0){
            max=heights[stack[top]]*i>max?heights[stack[top]]*i:max;
            top--;
            i--;
        }
    }
    return max;
}

发表于 2022-07-27 09:57:15 回复(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)

牛客38477449号

class Solution:
    def largestRectangleArea(self , heights: List[int]) -> int:
        # write code here
        if len(heights) == 0:
            return 0
        if len(heights) == 1:
            return heights[0]
        stack = []
        res = 0
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                H = heights[stack.pop()]
                L = 0 if not stack else stack[-1] + 1
                res = max(res, H * (i - L))
            stack.append(i)
        while stack:
            H = heights[stack.pop()]
            L = 0 if not stack else stack[-1] + 1
            res = max(res, H * (len(heights) - L))
        return res

发表于 2021-12-24 18:08:53 回复(0)