1. 知识点总结

题目	难度	知识点
单词搜索	🐸	DFS
柱状图中的最大矩形	🐸🐸🐸	单调栈

2. 分题题解

2.1 单词搜索

基础的DFS,注意剪枝

class Solution {
public:
    vector<vector<char>>mp;
    vector<vector<char>>vis;
    string str;
    int m,n;
    int len;
    bool ans;
    //四个方向
    vector<int>dx={0,0,1,-1};
    vector<int>dy={1,-1,0,0};
    void dfs(int x,int y,int id){
        vis[x][y]=true;
        if(id==len-1){
            ans=true;
        }else{
            id++;
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&!vis[nx][ny]&&str[id]==mp[nx][ny]){
                    //满足：不越界；没有访问过；字符匹配
                    dfs(nx,ny,id);
                }
            }
        }
        vis[x][y]=false;//回溯

    }
    bool exist(vector<vector<char>>& board, string word) {
        mp=board;
        len=word.length();
        m=board.size();
        n=board[0].size();
        vis.resize(m);
        for(int i=0;i<m;i++){
            vis[i].resize(n);
            fill(vis[i].begin(),vis[i].end(),false);
        }
        str=word;
        ans=false;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]==word[0]){
                    dfs(i,j,0);
                    if(ans){
                        return ans;
                    }
                }
            }
        }
        return ans;
    }
};

2.2 柱状图中的最大矩形

一开始想到的是简答的暴力算法，伪DP了属于~然后超时了(￣▽￣)￥

官方题解给的是单调栈，也就是O(n+n)的时间复杂度

其实题目可以简化为：对某一个height[i]求它的左右两边不低于它的高度的limit_index，而这个limit_index的求法就是单调栈啦，栈里面存的是下标索引

1、暴力解法：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        //DP存储[i,j]区间矩形的面积
        int len=heights.size();
        vector<vector<int> >dp(len,vector<int>(len));
        //初始化
        int ans;
        for(int i=0;i<len;i++){
            fill(dp[i].begin(),dp[i].end(),0);
            dp[i][i]=heights[i];
            if(ans<heights[i]){
                ans=heights[i];
            }
        }
        //计算所有的高度
        int h;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
              h=dp[i][j-1]/(j-i);//之前的高度  
              dp[i][j]=min(h,heights[j])*(j-i+1);
              if(dp[i][j]>ans){
                  ans=dp[i][j];
              }
            }
        }
        return ans;
    }
};

2、单调栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len=heights.size();
        stack<int>st;
        vector<int>left(len);vector<int>right(len);
        for(int i=0;i<len;i++){
            while(!st.empty()&&heights[st.top()]>=heights[i]){
                st.pop();
            }
            left[i]=(st.empty()?-1:st.top());
            st.push(i);
        }
        while(!st.empty()){
            st.pop();
        }
        for(int i=len-1;i>=0;i--){
            while(!st.empty()&&heights[st.top()]>=heights[i]){
                st.pop();
            }
            right[i]=(st.empty()?len:st.top());
            st.push(i);
        }
        //遍历
        int ans=0;
        for(int i=0;i<len;i++){
            ans=max(ans,(right[i]-left[i]-1)*heights[i]);
        }
        return ans;
    }
};