柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> minLeftIndex(heights.size());
        vector<int> minRightIndex(heights.size());
        int size = heights.size();

        // 记录每个柱子 左边第一个小于该柱子的下标
        minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环
        for (int i = 1; i < size; i++) {
            int t = i - 1;
            // 这里不是用if，而是不断向左寻找的过程
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        // 记录每个柱子 右边第一个小于该柱子的下标
        minRightIndex[size - 1] = size; // 注意这里初始化，防止下面while死循环
        for (int i = size - 2; i >= 0; i--) {
            int t = i + 1;
            // 这里不是用if，而是不断向右寻找的过程
            while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];
            minRightIndex[i] = t;
        }
        // 求和
        int result = 0;
        for (int i = 0; i < size; i++) {
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            result = max(sum, result);
        }
        return result;
    }
};


class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {            // 单调栈    思想还是找到左边第一个比柱子小以及右边第一个比柱子小的   
        int result=0;                                             //  while(!st.empty()&&heights[i]<heights[st.top()]){这行代码就代表找到了右边第一个最小的，然后不断的st.pop()
        stack<int> st;                                            //  st.pop() 之后如果 if(!st.empty()){还有的话  那么栈顶就是左边第一个最小的下标。
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        st.push(0);
        for(int i=1;i<heights.size();i++){
            while(!st.empty()&&heights[i]<heights[st.top()]){
                int mid=st.top();
                st.pop();
                if(!st.empty()){
                    result=max(result, heights[mid]*(i-st.top()-1));
                }
            }
            st.push(i);
        }
        return result;
    }
};