直方图中的最大矩形_

WangYu_

/*
目的：用height[]构造一个升序栈,构造过程中计算面积；
如果当前height[i]大于栈顶元素，则入栈；
若小于栈顶元素，则将栈顶元素弹出并做记录弹出几次，并计算以弹出元素作为高度的面积，留下
最大值ret，直到满足height[i]大于栈顶元素，再将弹出的元素以height[i]重新入栈；
    过程为 ：
    1）2入栈；目前栈为{2}
    2）1与2比较，不满足升序，则2弹出，记录count=1；ret=2*1；
       1代替2再次入栈，然后当前1入栈；目前栈为{1,1}
    3）5入栈，满足升序，6入栈满足升序；目前栈为{1,1,5,6,}
    4）height[4]=2，即将入栈，由于2小于栈顶元素6，则6弹出，count=1，ret=max（2,6）=6；
       2小于5,5弹出，count=2,ret=max(6,2*5)=10;
       6和5 重新以2入栈，然后height[4]=2入栈；
       目前栈为{1,1,2,2,2}
    5）height[5]=3入栈；形成升序栈{1,1,2,2,2,3}
    6）最后按照升序栈继续维护ret直至栈为空，max(ret,3*1,2*2,2*3,2*4*,1*5,1*6)=10;
*/
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int ret=0;
        stack<int> stk;
        for(int i=0;i<height.size();i++)
        {
            if(stk.empty()||(stk.top()<=height[i]))
                stk.push(height[i]);
            else
            {
                int count=0;
                while(!stk.empty()&&height[i]<stk.top())
                {
                    count++;
                    ret=max(ret,count*stk.top());
                    stk.pop();
                }
                while(count--)
                    stk.push(height[i]);
                stk.push(height[i]);
            }
        }
        int count=1;
        while(!stk.empty())
        {
            ret=max(ret,stk.top()*count);
            stk.pop();
            count++;
        }
        return ret;
    }
};

发表于 2017-10-12 10:43:17 回复(14)

wanlanwalan

/*
用堆栈计算每一块板能延伸到的左右边界
对每一块板
 堆栈顶矮，这一块左边界确定，入栈
 堆栈顶高，堆栈顶右边界确定，出栈，计算面积
 入栈时左边界确定
 出栈时右边界确定
 堆栈里元素是递增的
本质：中间的短板没有用！
复杂度 O(n)
*/
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int n=height.size(),result=0;
        stack<int> s;
        for(int i=0;i<n;++i){
            while((!s.empty())&&(height[s.top()]>=height[i])){
                int h=height[s.top()];
                s.pop();
                result=max(result,(i-1-(s.empty()?(-1):s.top()))*h);
            }
            s.push(i);
        }
        while(!s.empty()){
            int h=height[s.top()];
            s.pop();
            result=max(result,(n-1-(s.empty()?(-1):s.top()))*h);
        }
        return result;
    }
};

发表于 2017-07-20 15:20:03 回复(11)

JacobGo！

/*
	 * Runtime: 24 ms.Your runtime beats 67.12 % of java submissions.
	 */
	public int largestRectangleArea(int[] heights) {
		if (heights == null || heights.length < 1)
			return 0;

		Stack<Integer> stack = new Stack<Integer>();
		stack.push(-1);
		int max = 0;
		for (int i = 0; i < heights.length; i++) {
			while (stack.peek() != -1 && heights[i] < heights[stack.peek()]) {
				int top = stack.pop();
				max = Math.max(max, (i - stack.peek() - 1) * heights[top]);
			}
			stack.push(i);
		}
		while (stack.peek() != -1) {
			int top = stack.pop();
			max = Math.max(max, (heights.length - 1 - stack.peek()) * heights[top]);
		}
		return max;
	}

发表于 2017-07-02 13:48:10 回复(0)

啊哟嘿

最简单的一个一个比较，时间复杂度比较大。如果使用堆栈时间复杂度会小很多。

 public int largestRectangleArea(int[] height) {
        int n = height.length;
        int max = 0;
        for(int i=0;i<n;i++){
            int thisMinHeight = height[i];
            int width = 0;
            for(int j=i;j<n;j++){
                width++;
                thisMinHeight = Math.min(thisMinHeight,height[j]);
                max = Math.max(max,thisMinHeight*width);
            }
        }
        return max;
    }

发表于 2017-12-29 15:10:42 回复(0)

Java

卖萌の哈士奇

//以height的每个数作为基准来构建长方形，即从第i个值往前查找连续N个大于等于height[i]的值，
//往后查找M个大于等于height[i]的值，即可以构建一个(M+N+1) * height[i]的长方形
//取其中面积最大的一个
public class Solution {
    public int largestRectangleArea(int[] height) {
        int max = 0;
        for(int i = 0; i < height.length; i++){
            int len = 1;
            for(int j = i - 1; j >= 0; j--){
                if(height[j] >= height[i]){
                    len++;
                }else {
                    break;
                }
            }
            for(int k = i + 1; k < height.length; k++){
                if(height[k] >= height[i]){
                    len++;
                }else {
                    break;
                }
            }
            max = Math.max(max,len * height[i]);
        }
        return max;
    }
}

发表于 2017-09-05 20:04:03 回复(1)

C/C++

J.Fan

//这里主要思路是遇到比上升序列就入栈，遇到下降序列就计算当前前一个直方图(即当前栈顶序号)
//到所有依次出栈（即降序且大于j指向直方图的高度）直方图的距离，然后乘以出栈直方图的高度，
//即为当前的面积(不一定最大),剩下的序列依然是升序的，迭代下去
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int maxS = 0;
        int len = height.size();
        stack<int> st;
        st.push(-1);
        int num;
        for(int i=0;i<len;i++)
        {
            while(st.top()!=-1 && height[i]<height[st.top()])
            {
                num = st.top();
                st.pop();
                maxS = max(maxS,(i-1-st.top())*height[num]);
            }
            st.push(i);
        }
        while(st.top()!=-1)
        {
            num = st.top();
            st.pop();
            maxS = max(maxS,(len-1-st.top())*height[num]);
        }
        return maxS;
    }
};

发表于 2019-01-08 19:45:06 回复(0)

欢聚内推小哥

看别的答案，写得我懵逼，自己调试了一遍，在这里写下自己的理解

    public int largestRectangleArea(int[] height) {
        int result=0;
        Stack<Integer> stack=new Stack<>();
        int len=height.length;
        for(int i=0;i<len;i++){
            //栈中存储的是递增高度对应的index
            if(stack.empty()||height[stack.peek()]<=height[i])
                stack.push(i);
            else{
                //碰到不满足递增的就干掉比当前高度大对应的index，直到当前高对应的index可以入栈
                int high= height[stack.pop()];
                //stack.peek()+1确定左边界，右边界是i，公式=高*(右边界-左边界)
                int width=stack.empty()?i:i-stack.peek()-1;
                result= Math.max(result,high*width);
                i--;
            }
        }
        while(!stack.empty()){
            int index = stack.pop();
            int high=height[index];
            //之前***掉的也比当前的高度高，所以也被包括在左右边界之间
            int width=stack.empty()?len:len-stack.peek()-1;
            result=Math.max(result,high*width);
        }
        return result;
    }

发表于 2018-04-11 00:46:13 回复(0)

C/C++

华科不平凡

单调栈的最典型用法，下面的代码可以作为单调栈的模版进行记忆：

注意其中第18行在数组最后添加了一个0，这么做可以保证遍历最后一个元素时栈被清空，大大简化了代码

//
// Created by jt on 2020/9/24.
//
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    /**
     *
     * @param height int整型vector
     * @return int整型
     */
    int largestRectangleArea(vector<int>& height) {
        // write code here
        stack<int> stk;
        height.push_back(0);  // 简化代码，确保栈最后会被清空
        int maxVal = 0;
        for (int i = 0; i < height.size(); ++i) {
            while (!stk.empty() && height[i] < height[stk.top()]) {
                int h = height[stk.top()]; stk.pop();
                int leftIdx = stk.empty() ? -1 : stk.top();
                int w = i - leftIdx - 1;
                maxVal = max(maxVal, h * w);
            }
            stk.push(i);
        }
        return maxVal;
    }
};

发表于 2020-09-24 16:26:49 回复(0)

实在学不动了

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        if(height.empty()) return 0;
        int maxarea=INT_MIN;
        set<int> ST(height.begin(),height.end());
        for(set<int>::iterator i=ST.begin();i!=ST.end();i++) {
            int area=0;
            for(int j=0;j<height.size();j++) {
                if(height[j]>=*i) area+=*i;
                else {
                    maxarea=max(maxarea,area);
                    area=0;
                }
            }
            maxarea=max(maxarea,area);
        }
        return maxarea;
    }
};用一个高度作为基准线，只要高于基准线，就将面积加上基准线高度；低于基准线就先将前面得到的面积储存起来，再继续测算；
这些基准线集合是包括整个数组里面不重复的值的集合，当把整个基准线集合计算完毕后，就可以得出最大面积。

发表于 2020-05-08 11:46:19 回复(0)

tuweilong

/*
看了很久使用栈的题解，一直无法理解。
我这个贪心算法很容易理解。
遍历数组，认为当前值为答案的最低点。
向左找当前值大的，向右找比当前值大的。
*/
public class Solution {
    public int largestRectangleArea(int[] height) {
        int len = height.length;
        if (len == 0) return 0;
        int width = 0;
        int left = 0, right = 0;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            width = 1;
            left = i - 1;
            right = i + 1;
            while (left >= 0 && height[left] >= height[i]) {
                width++;
                left--;
            }
            while (right < len && height[right] >= height[i]) {
                width++;
                right++;
            }
            ans = Math.max(ans, height[i]*width);
        }
        return ans;
    }
}

发表于 2019-06-25 11:09:01 回复(2)

进击的雨滴

/****，先看到了上一道题，，，发现没有任何的思路，要怀疑人生，网上找各种解析
也发现根本看不懂，直到我点了下一道才发现要先坐着道题，这道题比上一道简单一
些，利用网上大神们的栈的思路，觉得非常吊记录一下思路：利用一个栈去实现将数组有序化，每次遍历数组都去与栈顶做对比，
如果发现比栈顶大则说明满足顺序直接入栈，如果没有栈顶元素值大，那就将栈顶出
栈，并计算当前result=max(result,count*top())。(注意这里，如果当前栈顶依然比较大，继续保
存result，弹出栈顶，此时的count值应该为当前栈顶元素值，在之前弹出的值都是比
该值大，计算面积的时候应该也计算到之前弹出的值。最后当所有元素遍历结束后，再
判断result中的值与直方图底部满足排序顺序的面积最大值进行对比即可
**/
class Solution {
public:
    ;
    int largestRectangleArea(vector &height) {
        int result = 0;
        stack st;
        for (auto it = height.begin(); it != height.end(); ++it)
        {
            if (st.empty() || st.top() <= *it)
                st.push(*it);
            else
            {
                int count = 0;
                while (!st.empty() && st.top() > *it)
                {
                    // [](int a, int b) -> bool { return a < b; }
                    count++;
                    result = result > count*st.top() ? result : count*st.top();
                    st.pop();
                }
                while (count-- > 0)
                {
                    st.push(*it);
                }
                st.push(*it);
            }
        }
        for (int i = 0; i < height.size(); i++)
        {
            int com = st.top() * (i+1);
            st.pop();
            result = result > com ? result : com;
        }
        return result;
    }
};

编辑于 2019-03-02 15:45:29 回复(1)

ID84848484

//时间复杂度很大，不过自己写的
//加油

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int len=height.size();
        if(len<=0)
            return 0;
        int sum[1000][1000]={0};
        int tem;
        int m=0;
        for(int i=0;i<len;i++){
            sum[i][0]=height[0];
            tem=height[i];
            for(int j=i+1;j<len;j++){
                tem=min(tem,height[j]);
                sum[i][j]=tem*(j-i+1);
                if(sum[i][j]>m)
                    m=sum[i][j];
            }
        }
        int ans= *max_element(height.begin(),height.end());
        return ans > m ? ans:m;
    }
};

发表于 2018-09-09 17:01:22 回复(0)

明年春招我一定能拿到大厂offer!!

//思路:单调栈
//维护一个单调递增的栈，l,r代表该pos的左右边界(l,r为下标)
//例如:2,1,5,6,2,3
//2的左右边界为(0,0)即2在这个区间保持最小
//1就是(0,5)
//最后算面积就是(p.r+1-p.l)*p.h
class _103{
    static class area{
        int l;
        int r;
        int h;
        int index;
    }
    public int largestRectangleArea(int[] height) {
        area[] t=new area[height.length];
        Stack<area> st=new Stack<area>();
        for (int i = 0; i < height.length; i++) {
            t[i]=new area();
            t[i].l=i;
            t[i].index=i;
            t[i].h=height[i];
        }
        for (int i = 0; i < height.length; i++) {
            while (!st.isEmpty()&&st.peek().h>t[i].h){
                t[st.peek().index].r=i-1;
                t[i].l=st.peek().l;
                st.pop();
            }
            st.push(t[i]);
        }
        while (!st.isEmpty()){
            st.pop().r=height.length-1;
        }
        int max=0;
        for (int i = 0; i < height.length; i++) {
            max=Math.max(max,(t[i].r+1-t[i].l)*t[i].h);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] a={2,1,5,6,2,3};
        System.out.println(new _103().largestRectangleArea(a));
    }
}

编辑于 2018-08-27 16:29:17 回复(0)

SunnyMarkLiu

package largest_rectangle_in_histogram;

/**
 * 容器装水问题
 * Given n non-negative integers representing the histogram's bar height
 * where the width of each bar is 1, find the area of largest rectangle
 * in the histogram.
 */
public class Solution {

    /**
     * 暴力搜索，从左到右扫描边界，针对每个边界扫描左边的矩阵，计算面积，
     * 注意保留最小高度和最大面积，时间复杂度 O(n^2)
     */
    public int largestRectangleArea1(int[] height) {
        if (height == null || height.length == 0)
            return 0;

        int maxArea = 0;
        for (int boundary = 0; boundary < height.length; boundary++) {
            int minHeight = height[boundary];

            // 从右边界到左扫描计算面积，保存最大值
            for (int left = boundary; left >= 0; left--) {
                minHeight = Math.min(minHeight, height[left]);
                int area = minHeight * (boundary - left + 1);
                if (area > maxArea)
                    maxArea = area;
            }
        }
        return maxArea;
    }

    /**
     * 暴力搜索，从左到右扫描边界，针对每个边界扫描左边的矩阵，计算面积，
     * 注意保留最小高度和最大面积，时间复杂度 O(n^2)
     */
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0)
            return 0;

        int maxArea = 0;
        for (int boundary = 0; boundary < height.length; boundary++) {

            // 暴力搜索优化的地方，对于 boundary 递增序列的情况，可 continue
            if (boundary < height.length - 1 && height[boundary] <= height[boundary+1])
                continue;

            int minHeight = height[boundary];

            // 从右边界到左扫描计算面积，保存最大值
            for (int left = boundary; left >= 0; left--) {
                minHeight = Math.min(minHeight, height[left]);
                int area = minHeight * (boundary - left + 1);
                if (area > maxArea)
                    maxArea = area;
            }
        }
        return maxArea;
    }
}

发表于 2018-08-25 12:26:40 回复(0)

潘多拉Boot

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int S=0;
        for(int i=0;i<height.size();i++){     //从第i个元素开始往前连续找m个比height[i]大的元素，
            int len=1;                        //从i个元素开始往后连续找n个比height[i]大的元素，
            for(int j=i-1;j>=0;j--){          //矩形的长度就是 m+n+1,高度就是height[i],面积相乘即可
                if(height[i]<=height[j])len++;
                else break;
            }
            for(int k=i+1;k<height.size();k++){
                if(height[i]<=height[k])len++;
                else break;
            }
            S=max(S,len*height[i]);
        }
        return S;
    }
};

发表于 2018-04-24 17:02:33 回复(0)

C/C++

nbgao

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int n = height.size();
        if(n == 0)
        	return 0;
        vector<int> dp = height;
        int s = dp[0];
        for(int i=1;i<n;i++)
        {
        	int temp = height[i];
        	for(int j=i-1;j>=0 && height[j]>0;j--)
        	{
        		temp = min(temp,height[j]);
        		dp[i] = max(dp[i],temp*(i-j+1));
			}
			s = max(s,dp[i]);
		}
		return s;
    }
};

发表于 2017-08-19 04:12:57 回复(0)

Java

SnailLLL

//类似于中心拓展法，针对每个位置，找到前后大于等于该高度元素的数量
public class Solution {
    /**
     * 
     * @param height int整型一维数组 
     * @return int整型
     */
    public int largestRectangleArea (int[] height) {
        // write code here
        int max=0;
        int l=height.length;
        for(int i=0;i<l;i++){
            int low=i;
            int high=i;
            int sum=-1;
            while(low>=0 && height[low]>=height[i]){
                sum++;
                low--;
            }
            while(high<l && height[high]>=height[i]){
                sum++;
                high++;
            }
            max=Math.max(max,sum*height[i]);
        }
        return max;
    }
}

发表于 2021-06-02 11:30:00 回复(0)

科学xx

//暴力求解

public int largestRectangleArea (int[] height) {

if (height == null || height.length == 0){
return 0;
}
int max= -1;
for (int i = 0; i < height.length; i++) {
if (height[i] > max){
max = height[i];
}
int sum = 0;
int min = height[i];
for (int j = i+1; j < height.length; j++) {
min = Math.min(min,height[j]);
sum = (j-i+1)*min;
if (sum > max){
max = sum;
}
}
}
return max;
}

发表于 2020-08-15 15:15:59 回复(0)

iMi丶

    public int largestRectangleArea (int[] height) {
        
        if(height.length == 0 || height == null)
            return 0;
        
        int length = height.length;
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0 ; i < length ; i++){
            while( !stack.isEmpty() && height[stack.peek()] >= height[i] ){
                //矩形高度
                int high = height[stack.pop()];
                //矩形左边界
                int leftIndex = stack.isEmpty() ? -1 : stack.peek() ;
                //矩形右边界
                int rightIndex = i - 1;
                //计算面积
                int curMax = high * (rightIndex - leftIndex );
                max = Math.max(max,curMax);
            }
            stack.push(i);
        }
        
        //当右边无比 栈顶 小的数时，剩余数全入栈，此时上面的循环未将栈中元素pop，即有矩形高度为height[stack.peek()]的元素未计算面积最大值
        while(!stack.isEmpty()){
                //矩形高度
                int high = height[stack.pop()];
                //矩形左边界
                int leftIndex = stack.isEmpty() ? -1 : stack.peek() ;
                //矩形右边界
                int rightIndex = length - 1;
                //计算面积
                int curMax = high * (rightIndex - leftIndex );
                max = Math.max(max,curMax);
        }
        return max;
    }

发表于 2020-07-24 15:19:53 回复(0)

林夕🇨🇳（字节搜索研发急招实习）

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack=new Stack<>();//栈 维护宽度
        stack.push(-1);//入一个-1保证最小
        int maxarea=0;
        for(int i=0;i<heights.length;++i){
            while(stack.peek()!=-1&&heights[stack.peek()]>=heights[i])//如果这个比栈顶小，栈顶出栈，更新maxarea
              maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
            stack.push(i);//i入栈，成为现在栈顶，也是最大
            
        }
        while(stack.peek()!=-1)//边界 全出
            maxarea=Math.max(maxarea,heights[stack.pop()]*(heights.length-stack.peek()-1));
        return maxarea;
        
    }
}

发表于 2020-05-03 14:48:06 回复(0)

直方图中的最大矩形

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题