84. Largest Rectangle in Histogram

第一版：超时,双层循环。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty())
        {
            return 0;
        }
        int result = heights.front();
        
        vector<int> min_record;
        for(int i = 0; i < heights.size(); ++i)
        {
            int min = heights[i];
            min_record.clear();
            for(int j = i; j < heights.size(); ++j)
            {
                if(min > heights[j])
                {
                    min = heights[j];
                }
                min_record.push_back(min);
            }
            int base = 0;
            //result = min_record[base];
            for(int j = base + 1; j < min_record.size(); ++j)
            {
                if(min_record[base] != min_record[j])
                {
                    int buffer = min_record[base] * (j - base);
                    if(result < buffer)
                    {
                        result = buffer;
                    }
                    base = j;
                }
                //如果最小值在最后一位变化，那么最后一位肯定不会产生最大面积，只有一个直方，不会进入此层循环。
                else if(j == min_record.size() - 1)
                {
                    int buffer = min_record[base] * (j - base + 1);
                    if(result < buffer)
                    {
                        result = buffer;
                    }
                }
            }
        }
        return result;
        
    }
};

看了看tag，用栈的话，加以优化。
Largest Rectangle in Histogram
= =才疏学浅，没想出来，贴上所查链接，以及参考所写代码如下：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty())
        {
            return 0;
        }
        int result = 0;
        stack<int> buf_stack;
        result = heights.front();
        buf_stack.push(heights.front());
        for(int i = 1; i < heights.size(); ++i)
        {
            if(heights[i] >= buf_stack.top())
            {
                buf_stack.push(heights[i]);
            }
            else
            {
                int count;
                for(count = 1; !buf_stack.empty() && buf_stack.top() > heights[i]; ++count )
                {
                    result = max(result,count * buf_stack.top());
                    buf_stack.pop();
                }
                while(count--)
                {
                    buf_stack.push(heights[i]);
                }
                
            }
        }
        for(int count = 1; !buf_stack.empty(); ++count )
        {
            result = max(result,count * buf_stack.top());
            buf_stack.pop();
        }
        return result;
    }
};

AC！撒花！