2020-08-27 刷题3 动态规划&&深度优先搜索

84 柱状图中的最大矩形

每个高度的矩形宽度取决于向左数第一个不大于这个高度的位置，和向右数第一个小于这个高度的位置的距离。
用单调栈，栈顶元素为最大值。每次遍历到第i个位置时，如果它的高度大于栈顶元素，说明这个柱子前的柱子高度都没有它高，因此还无法确定这个高度矩形大小，直接将其入栈；但如果低于栈顶的元素，那么栈顶元素的高度对应矩形就可以确定了，这个元素可以出栈，左边界是当前栈顶元素的位置或者数组开头。
这里在数组最后添加了一个哨兵0，是一个非常好用的技巧，可以避免一些条件判断。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        int i = 0;
        int max_size = 0;
        heights.push_back(0);
        while(i < heights.size()){
            while(!s.empty() && heights[s.top()] > heights[i]){
                int tmp = s.top();
                s.pop();
                int cur_size = heights[tmp] * (s.empty() ? i : (i - s.top() - 1));
                max_size = max(max_size, cur_size);
            }
            s.push(i);
            i++;
        }
        return max_size;
    }
};

85 最大矩形

这个题目是上一个题目的延续，首先将原来的数组转化成到每个位置为止的高度，这样每一行就变成了一个柱状图的高度，然后在每一行上运用84题的解法，求出最大的矩形面积。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        int i = 0;
        int max_size = 0;
        heights.push_back(0);
        while(i < heights.size()){
            while(!s.empty() && heights[s.top()] > heights[i]){
                int tmp = s.top();
                s.pop();
                int cur_size = heights[tmp] * (s.empty() ? i : (i - s.top() - 1));
                max_size = max(max_size, cur_size);
            }
            s.push(i);
            i++;
        }
        return max_size;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        vector<vector<int>> dp;
        if(matrix.size() == 0)
            return 0;
        int row_num = matrix.size(), col_num = matrix[0].size();
        for(int i = 0; i < row_num; i++){
            vector<int> a(col_num);
            for(int j = 0; j < col_num; j++){
                a[j] = matrix[i][j] - '0';
            }
            dp.push_back(a);
        }
        for(int i = 0; i < col_num; i++){
            for(int j = 1; j < row_num; j++){
                if(dp[j][i] > 0)
                    dp[j][i] = dp[j - 1][i] + 1;  
            }
        }
        int max_area = 0;
        for(int i = 0; i < row_num; i++){
            int cur_area = largestRectangleArea(dp[i]);
            max_area = max(max_area, cur_area);
        }
        return max_area;
    }
};

200 岛屿数量

深搜

class Solution {
public:
    void dp(vector<vector<char>>& grid, int i, int j){
        if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size())
            return;
        if(grid[i][j] == '0')
            return;
        grid[i][j] = '0';
        dp(grid, i - 1, j);
        dp(grid, i + 1, j);
        dp(grid, i, j - 1);
        dp(grid, i, j + 1);
    }
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size() == 0)
            return 0;
        int island = 0, row_num = grid.size(), col_num = grid[0].size();
        for(int i = 0; i < row_num; i++){
            for(int j = 0; j < col_num; j++){
                if(grid[i][j] == '1'){
                    dp(grid, i, j);
                    island++;
                }
            }
        }
        return island;
    }
};