题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积
解题思路
思路一：暴力寻找，从每个位置出发，向左右两边扩散查找，若发现柱形比当前位置高，则宽度加一，组成长方形，代码实现如下，但是提交之后发现在极端情况下会超时
public int largestRectangleArea(int[] heights) {int res = 0;for (int i = 0; i < heights.length; i++) {int height = heights[i], wid = 1;for (int j = i + 1; j < heights.length; j++) {if (heights[j] < height) break;else {wid++;}}for (int j = i - 1; j >= 0; j--) {if (heights[j] < height) break;else {wid++;}}res = Math.max(res, height * wid);}return res;}
算法优化
在暴力查询的基础上，研究发现，在某些情况下，可以前置信息来加速后续的查询，也就是说，可以使用动态规划来解题。使用zuo[i]数组表示从0到i，柱状图中以heights[i]为高的最大矩形宽度，从左向右遍历一次，使用you[i]数组表示从i到 len -1(终点位置)，柱状图中以heights[i]为高的最大矩形宽度，再遍历一次。
注意！！，第二次遍历时，也就是从i到 len -1(终点位置)，向右寻找柱状图中以heights[i]为高的最大矩形时，我们更新最大面积时记得加上前一次求出的左边宽度zuo[i]数
代码实现
class Solution {public int largestRectangleArea(int[] heights) {int res = heights[0];int[] zuo = new int[heights.length], you = new int[heights.length];zuo[0] = 1;you[heights.length - 1] = 1;for (int i = 1; i < heights.length; i++) {int height = heights[i], wid = 1;int j = i - 1;while (j >= 0) {if (heights[j] < height) {break;} else {wid += zuo[j];j = j - zuo[j];}}zuo[i] = wid;res = Math.max(res, height * wid);}for (int i = heights.length - 2; i >= 0; i--) {int height = heights[i], wid = 1;int j = i + 1;while (j < heights.length) {if (heights[j] < height) break;else {wid += you[j];j = j + you[j];}}you[i] = wid;if (i > 0) wid = (wid + zuo[i] -1);res = Math.max(res, height * wid);}return res;}
}
算法效果
