一天一道LeetCode
（一）题目
（二）解题
题目大意：给定一个含有高度值的数组，表示一个直方图，求这组直方图中最大矩阵的面积
解题思路：对于每一个高度值，往左边比它大的话宽度就+1，否则就停止查找，再往右找比它大的话宽度就+1，否则就停止查找，这样就可以计算已当前高度值为高度的最大矩阵面积。
例如：已图中1为例，往左边找比它大的只有1个，往右边找比它大的有4个，这样以1为高度的矩阵宽度为6，这样的话面积为6
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int max = 0;
for(int i = 0 ; i < heights.size() ; i++)
{
int count = 1;
int j = i -1;
while(j>=0&&heights[j--]>heights[i]) count++;//往左边找
j = i+1;
while(j<heights.size()&&heights[j++]>heights[i]) count++;//往右边找
int area = heights[i]*count;
max = max>area?max:area;//计算面积
}
return max;
}
};这样做的结果当然是 Time Limit Exceeded！！！
只能继续想办法！
大家可以注意到，每一次往左边找的时候，很多信息都可以利用。
以题目图中的1为例，我们的目的是为了找出1的右边有多少个比它大，
这个时候5的左边有1个比它大，那么就可以跳过6直接看2是否比它大，
然后2的后边3比它大，又可以跳过3。
然后就可以计算出来1的右边有4个比它大！
所以采用两个数组来记录查找过的每一个高度值左/右边比它小的个数。这就是这个算法的重要优化思想！
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int size = heights.size();
int max= 0;
vector<int> left(size,0);//记录左边比heights[i]大的高度值个数
vector<int> right(size,0);//记录右边比heights[i]大的高度值个数
for(int i = 1 ; i < size ; i++)
{
int j = i-1;
while(j>=0&&heights[j]>=heights[i]) j-=(left[j]+1);//可以跳过left[i]个数，简化了算法的时间复杂度
left[i] = i-j-1;
}
for(int i = size-2; i>=0 ; i--)
{
int j = i+1;
while(j<size&&heights[j]>=heights[i]) j+=(right[j]+1);//同上
right[i] = j-i-1;
}
for(int i = 0 ; i < size ; i++){
int area = (left[i]+right[i]+1)*heights[i];//计算面积
max = max>area?max:area;//取最大
}
return max;
}
};