Leetcode 84. Largest Rectangle in Historam

难度: Hard

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.

Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area =10 unit.

For example,Given heights = [2,1,5,6,2,3],return 10.

首先我想到的是 遍历整个vector 然后向前向后遍历 如果找到了比当前位置的元素小的位置的话 就停止 然后计算前后坐标的差 即需要计算的长度 再用当前的值乘以这个长度 进行比较 最后得出最大的面积

不出所料 时间超过限制

于是优化了算法

class Solution {public:int largestRectangleArea(vector<int>& height) { stack<int> S;       height.push_back(0);         int sum = 0;         int length=height.size();      for (int i = 0; i < length; i++) {              if (S.empty() || height[i] > height[S.top()])             S.push(i);              else {                   int temp = S.top();                   S.pop();                   int Index=0;                 if(S.empty())                 Index=i;                 else                 Index=i-1-S.top();                 sum=max(sum,height[temp]*Index);                 i--;              }         }         return sum; }};首先建立一个stack（存储的是元素的下标）  确立了基准以后 往后遍历 如果碰到了比它要大的元素 就将其的下标压进栈 这样我们就得到了一个严格递增的栈
这样做的好处是 无论怎样遍历 栈顶都是目前来看的最大元素 也就是说遍历到的所有元素 栈顶下标所对应的元素是最大的
如果遍历到的元素比栈顶元素小 就进行计算 将前面的栈内元素都计算一遍 然后进行比较
这个算法的时间复杂度是O（n）