84 柱狀圖中的最大矩形

每個(gè)高度的矩形寬度取決于向左數(shù)第一個(gè)不大于這個(gè)高度的位置，和向右數(shù)第一個(gè)小于這個(gè)高度的位置的距離。
用單調(diào)棧，棧頂元素為最大值。每次遍歷到第i個(gè)位置時(shí)，如果它的高度大于棧頂元素，說明這個(gè)柱子前的柱子高度都沒有它高，因此還無法確定這個(gè)高度矩形大小，直接將其入棧；但如果低于棧頂?shù)脑?，那么棧頂元素的高度?duì)應(yīng)矩形就可以確定了，這個(gè)元素可以出棧，左邊界是當(dāng)前棧頂元素的位置或者數(shù)組開頭。
這里在數(shù)組最后添加了一個(gè)哨兵0，是一個(gè)非常好用的技巧，可以避免一些條件判斷。

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 最大矩形

這個(gè)題目是上一個(gè)題目的延續(xù)，首先將原來的數(shù)組轉(zhuǎn)化成到每個(gè)位置為止的高度，這樣每一行就變成了一個(gè)柱狀圖的高度，然后在每一行上運(yùn)用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 島嶼數(shù)量

深搜

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;
    }
};