Leetcode84.柱状图中最大的矩形（困难）-创新互联

一、题目 1、题目描述

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

创新互联专注于淅川企业网站建设,成都响应式网站建设公司,商城网站建设。淅川网站建设公司,为淅川等地区提供建站服务。全流程定制制作，专业设计，全程项目跟踪，创新互联专业和态度为您提供的服务

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

示例1：

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

示例2：

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

2、基础框架

class Solution {public:
    int largestRectangleArea(vector& heights) {}
};

3、原题链接

84. 柱状图中大的矩形

二、解题报告 1、思路分析

例子：

那么大的长方形面积是如下图中的红色区域：

整体思路就是 必须以每个位置的直方图作为高的长方形能扩多远，遇到相同的高度时进行错化处理，最终是能计算正确的。

如何找到以每个位置的直方图作为高的长方形能扩充的范围呢？

找到每个位置左右最近的比它矮的直方图，除了这两个位置不能到达，其他位置就是它所能扩充的范围。

2、时间复杂度

O ( n ) O(n) O(n)

3、代码详解

• C++版

//不使用系统stack的解法
class Solution {public:
    int largestRectangleArea(vector& heights) {if (heights.size() == 0) return 0;

        int n = heights.size();

        int _stack[n]; //准备一个栈，此处使用数组替代系统栈
        memset(_stack, 0, sizeof(_stack));

        int si = -1;

        int ans = 0;

        for (int i = 0; i< n; i++) {while (si != -1 && heights[_stack[si]] >= heights[i]) {//栈不为空 且 栈顶元素对应的值>=当前元素位置对应的值
                int cur = heights[_stack[si--]]; //获取栈顶位置的直方图高度
                int left = si == -1 ? -1 : _stack[si]; //找到左边最近的比栈顶位置直方图低的位置
                ans = max(ans, (i - left - 1) * cur); //右边最近的比栈顶位置直方图低的是i位置
                //所以以cur为高度的长方形能扩充的范围就是[left + 1, i - 1],宽度为(i - left - 1)
            }
            _stack[++si] = i;
        }

        while (si != -1) {//遍历完数组后，栈中还有数据，则单独结算
            int cur = heights[_stack[si--]];
            int left = si == -1 ? -1 : _stack[si];
            ans = max(ans, (n - left - 1) * cur);
        }

        return ans;
    }
};

//使用系统stack的解法
class Solution {public:
    int largestRectangleArea(vector& heights) {if (heights.size() == 0) return 0;

        stacksta;
        int area = 0;
        for (int i = 0; i< heights.size(); i++) {while (!sta.empty() && heights[sta.top()] >= heights[i]) {int j = sta.top();
                sta.pop();
                int k = sta.empty() ? -1 : sta.top();
                area = max(area, (i - k - 1) * heights[j]);
            }
            sta.push(i);
        }

        while (!sta.empty()) {int j = sta.top();
            sta.pop();
            int k = sta.empty() ? -1 : sta.top();
            int curArea = (heights.size() - k - 1) * heights[j];
            area = max(area, curArea);
        }
        return area;
    }
};

• Java 版

public class LargestRectangleInHistogram {//使用系统栈
	public static int largestRectangleArea1(int[] height) {if (height == null || height.length == 0) {	return 0;
		}
		int maxArea = 0;
		Stackstack = new Stack();
		for (int i = 0; i< height.length; i++) {	while (!stack.isEmpty() && height[i]<= height[stack.peek()]) {		int j = stack.pop();
				int k = stack.isEmpty() ? -1 : stack.peek();
				int curArea = (i - k - 1) * height[j];
				maxArea = Math.max(maxArea, curArea);
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {	int j = stack.pop();
			int k = stack.isEmpty() ? -1 : stack.peek();
			int curArea = (height.length - k - 1) * height[j];
			maxArea = Math.max(maxArea, curArea);
		}
		return maxArea;
	}
	
	//使用数组替代系统栈
	public static int largestRectangleArea2(int[] height) {if (height == null || height.length == 0) {	return 0;
		}
		int N = height.length;
		int[] stack = new int[N];
		int si = -1;
		int maxArea = 0;
		for (int i = 0; i< height.length; i++) {	while (si != -1 && height[i]<= height[stack[si]]) {		int j = stack[si--];
				int k = si == -1 ? -1 : stack[si];
				int curArea = (i - k - 1) * height[j];
				maxArea = Math.max(maxArea, curArea);
			}
			stack[++si] = i;
		}
		while (si != -1) {	int j = stack[si--];
			int k = si == -1 ? -1 : stack[si];
			int curArea = (height.length - k - 1) * height[j];
			maxArea = Math.max(maxArea, curArea);
		}
		return maxArea;
	}
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：Leetcode84.柱状图中最大的矩形（困难）-创新互联
URL分享：http://cdkjz.cn/article/jedsp.html