解题报告：LeetCode Largest Rectangle in Histogram（计算最大矩形面积）

题目出处：https://leetcode.com/problems/largest-rectangle-in-histogram/
题意描述：
给定n个非负的整数，代表n个依次相邻的宽度为1的柱形的高，求这些柱形所能形成的最大的矩形面积。

解决思路：
此题最直接最原始的做法就是扫描起点和终点，并随时更新最大面积，但是这样的做法的复杂度为O(n^2)，显然会超时，这里就不再贴代码了。

于是我们需要考虑怎么将复杂度降下来，一种想法是在求面积之前进行预处理，将每个整数左右的第一个比当前位置矮的柱形的下标lefi[i]，right[i]求出来。这样在计算时便可以在O(n)的时间内将问题解决。但是此时如果仍然使用最简单粗暴的求下标的方法的话求下标的复杂度仍然是O(n^2)，并没有对问题进行任何化简。因此我们需要想出线性时间的算法来预处理。如求解right[i]的一种想法是在扫描的过程中如果当前位置i比上一位置高，则暂时不求出当前位置的左右最低下标，而是将当前当前位置的下标压入栈中，如果当前位置比上一位置矮，则将栈顶的元素弹出，设该位置为pos，该位置的right[pos]=i，重复弹出直至栈顶的元素比当前位置i矮为止。同理求出left[i]则可将问题解决

但是问题还可以简化，在求解right[i]的过程中其实就可以顺便将left[i]求解出来，因为栈中的元素一定是按照高度从小到大的顺序排列的，所以在弹出栈顶元素之后，其左边第一个比它矮的柱形一定是弹出后位于栈顶的元素新的元素，因此就可以在一次扫描的过程中将right[i],left[i],area[i]求解出来。下面附上此时的CPP代码(由于可以直接算出面积，故在代码中并没有存储left[i]和right[i])：

int largestRectangleArea(vector<int>& height) {
    int len = height.size();
    height.push_back(0);
    stack<int> s;
    s.push(0);
    int ans = 0;
    for(int i = 1; i <= len; i ++)
    {
        while(! s.empty() && height[i] < height[s.top()])
        {
            int index = s.top();
            s.pop();
        ans = max(ans, height[index]*(i-1-(s.empty()?-1:s.top())));
        };
        s.push(i);
    };
    return ans;
};

此份代码在OJ上AC，但是其运行时间为24ms，虽然在C++中属于大众水平，但是在相比C代码，速度仍然后很大的提升，于是可将代码中的栈去掉，改用C中的数组，于是便可将代码修改为C代码，运行时间果然大大缩短，达到了8ms，下面附上代码。

int largestRectangleArea(int* height, int heightSize) {
    int len = heightSize;
    int s[30000] = {0};
    int pos = 1;
    int ans = 0;
    for(int i = 1; i < len; i ++)
    {
    　　while(pos > 0 && height[i] <= height[s[pos-1]])
    　　{
        　　int index = s[pos-1];
      　　  pos --;
   　　     int area = height[index]*(i-1-(pos == 0 ? -1 : (s[pos-1])));
       　　 if(area > ans)
          　　  ans = area;
    　　};
    　　s[pos ++] = i;
    };
    while(pos > 0)
    {
        int index = s[pos-1];
            pos --;
        int area = height[index]*(len-1-(pos == 0 ? -1 : (s[pos-1])));
        if(area > ans)
            ans = area;
    }
    return ans;
};

可见将代码转换为C代码之后操作稍微麻烦了一点点，尤其是最后还加入了一个特判，使得代码行数增加了许多，于是考虑精简代码，下面附上精简后的代码。

int largestRectangleArea(int* height, int heightSize) {
    int s[30000] = {0};
    int pos = 1, ans = 0;
    for(int i = 1; i <= heightSize; i ++){
        while(pos > 0 && (i == heightSize || height[i] <= height[s[pos-1]])){
            int index = s[-- pos];
            int area = height[index]*(i-1-(pos == 0 ? -1 : (s[pos-1])));
            if(area > ans)
                ans = area;
         }
         s[pos ++] = i;
     }
     return ans;
};