1. 知识点总结

题目	难度	知识点
不同的搜索二叉树	🐸	二叉树
中序遍历二叉树	🐸	二叉树的中序遍历
最大矩形	🐸🐸🐸	单调栈

不可以😪！！明明早上有多睡哎！

2. 分题题解

2.1 中序遍历二叉树

emm这个不难哈，不记得的话回去复习数据结构

2.2 最大矩形

参考上一篇的柱状图中最大矩形的官方题解，对每一列运用单调栈即可

class Solution {
public:
    
    int maximalRectangle(vector<vector<char>>& matrix) {
        int row,col;
        row=matrix.size();
        if(row==0){
            return 0;
        }else{
            col=matrix[0].size();
            vector<vector<int> >bars(row,vector<int>(col));
            //初始化bars
            for(int i=0;i<row;i++){
                fill(bars[i].begin(),bars[i].end(),0);
                for(int j=0;j<col;j++){
                    if(matrix[i][j]=='1'){
                        if(j){
                            bars[i][j]=bars[i][j-1]+1;
                        }else{
                            bars[i][j]=1;
                        }
                    }
                }
            }
            //复用最大矩形的模板
            int ans=0;
            for(int i=0;i<col;i++){
                stack<int>st;
                vector<int>up(row,0),down(row,0);
                for(int j=0;j<row;j++){
                    while(!st.empty()&&bars[st.top()][i]>=bars[j][i]){
                        st.pop();
                    }
                    up[j]=st.empty()?-1:st.top();
                    st.push(j);
                }
                while(!st.empty()){
                    st.pop();
                }
                for(int j=row-1;j>=0;j--){
                    while(!st.empty()&&bars[st.top()][i]>=bars[j][i]){
                        st.pop();
                    }
                    down[j]=st.empty()?row:st.top();
                    st.push(j);
                }
                //对于每一列单调栈求最大的矩形
                int max_size=0;
                for(int k=0;k<row;k++){
                    max_size=max((down[k]-up[k]-1)*bars[k][i],max_size);
                }
                ans=max(max_size,ans);
            }
            return ans;
        }
    }
};

2.3 搜索不同的二叉树

找规律的一道题，看数据量哈，暴力即可

class Solution {
public:
    
    int numTrees(int n) {
        if(n<=2){
            return n;
        }else{
            vector<int>v(n+1);
            v[0]=1;
            v[1]=1;
            v[2]=2;
            for(int i=3;i<=n;i++){
                for(int j=i-1;j>=0;j--){
                    v[i]+=v[j]*v[i-1-j];
                   
                }
                
            }
            return v[n];
        }
    }
};