leetcode 84 柱状图中最大矩形 / Largest Rectangle in Histogram

题目描述：

    自己想了想发现只有暴力做，但这题明显是有简便算法的，网上看了看主流的解法是用单调(递增)栈做，算法大概思想是：维护一个单调递增序列，当前元素大于栈顶元素时则进栈，当前元素小于栈定元素时则处理完前面元素能得到的最大值后在进栈。

    这种方法非常的巧妙，感觉应该是本题的最优解法了，比如你想用暴力做，max[i]代表从i号节点开始的最大矩形，对单个节点处理一次用时o(n)，对每个节点都跑一次就要用时o(n方）了，然而用单调栈做的时间复杂度只要o(n)就可以完成（每个元素进栈出栈一次），因为用单调栈做避免了大量的重复计算。

    还有一点需要理解的是这段代码：

res = max(res, height[cur] * (st.empty() ? i : (i - st.top() - 1)));

是如何计算当前矩形面积的，height[cur]明显是当前矩形的高度，当前矩形的长度是(i - 1)- st.top()  （想想为什么），具体代码如下：

class Solution {
	public:
		int largestRectangleArea(vector<int> &height) {
			int res = 0;
			stack<int> st;
			height.push_back(0);//把0压入栈，为处理最后一个元素用的小技巧
			for (int i = 0; i < height.size(); ++i) {
				if (st.empty() || height[st.top()] < height[i]) {
					st.push(i);
				} else {
					int cur = st.top(); st.pop();
					res = max(res, height[cur] * (st.empty() ? i : (i - st.top() - 1)));
					--i;
				}     
			}
			return res;
		}
	};

    还找到一种不需要栈的方法，思想跟上面类似，也是找到局部最大值，只是没用到栈：

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int res = 0;
        for (int i = 0; i < height.size(); ++i) {
            if (i + 1 < height.size() && height[i] <= height[i + 1]) {
                continue;
            }
            int minH = height[i];
            for (int j = i; j >= 0; --j) {//   /// 
                minH = min(minH, height[j]);
                int area = minH * (i - j + 1);
                res = max(res, area);
            }
        }
        return res;
    }
};

     感觉这种方法还是没有上面一种优秀，j每次都是搜索到0的（第10行），其实根本不用搜索到0，这时，用栈的优势就体现出来了。