leetcode-Largest Rectangle in Histogram

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

class Solution2
{
public:
    int largestRectangleArea(vector<int> &height) {
        height.push_back(0);
        int i = 0;
        int result = 0;
        stack<int> s;
        while (i < height.size())
        {
            if (s.empty() || height[i]>height[s.top()])
                s.push(i++);
            else
                //已经发现下标[i]的元素比栈顶元素(也就是下标[i-1]的元素)小了，所以栈顶元素(即[i-1]号)无法向右延伸了。
                //因此可以将其弹出了，并计算向左能延伸多远。
                
            {
                int tmp = s.top();
                s.pop();
                result = max(result, height[tmp] * (s.empty() ? i:i-s.top()-1));
            }
        }
        return result;
    }
};





class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> s;
        height.push_back(0);//将0硬插入数组作为最后一个直方图高度值，从而在i遍历到最后时能把栈中剩余的元素全弹出来。
        int result = 0;
        for (int i = 0; i < height.size();) {

            //只有i所遍历到的元素大于栈顶元素时才能入栈，相等都不行，以保证当前的栈顶元素是独一无二的孤峰，【直接相邻的】左右元素都比它小，这样它就没法左右延伸了
            //每次都是针对出栈的栈顶元素，看该元素对应的直方柱能左右延伸多远、最大构成多大的矩阵。
            if (s.empty() || height[i] > height[s.top()])//这里是将i所指的值与栈顶元素比，不是与直接相邻的上一个元素比。
                s.push(i++);
            else {
                int tmp = s.top();
                s.pop();
                //(1)要想通一点：站在当前处理的元素的角度来看，对于那些之前入过栈又跳出去的元素，肯定都是比自己值大的。
                //(2)栈中元素都是单调递增的。
                //(3)当向右没法延伸时（i所指元素不再大于当前栈顶元素）就开始出栈，并通过【i-s.top()-1】得出向左延伸时能延伸多远（s.top()即向左延伸时第一个比自己值小的立柱的x坐标。比自己值大的不可能还在栈内。）
                //从而计算当前出栈元素所能参与构成的最大矩阵。
                //(4)i-1所指的元素必定是当前的栈顶元素
                result = max(result, height[tmp] * (s.empty() ? i : i - s.top() - 1));
            }
        }
        return result;
    }
};
int main()
{
    Solution s;
    int a[] = { 1, 2, 4, 3, 2, 4 };
    vector<int> v(a, a + 6);
    cout << s.largestRectangleArea(v) << endl;
    return 0;
}