力扣 C++11题解系列-084 最大矩形

内容导航：

力扣 C++11题解系列-084 最大矩形

力扣题解之：最长公共前缀

LeetCode 力扣官方题解 - 1020. 飞地的数量

(力扣算法题-回文数)C语言定义的布尔类型函数为什么提示编译出错？

一、力扣 C++11题解系列-084 最大矩形

题目

给定一个仅包含0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。示例:输入:[  ["1","0","1","0","0"],  ["1","0","1","1","1"],  ["1","1","1","1","1"],  ["1","0","0","1","0"]]输出: 6

解题代码与测试

//// Created by tannzh on 2020/8/22.///* * 最大矩形给定一个仅包含0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。示例:输入:[  ["1","0","1","0","0"],  ["1","0","1","1","1"],  ["1","1","1","1","1"],  ["1","0","0","1","0"]]输出: 6 */#include <iostream>#include <vector>#include <stack>#include <algorithm>using std::max;using std::min;using std::stack;using std::vector;class Solution {public:    int maximalRectangle(vector<vector<char> > &matrix) {        if (matrix.empty()) return 0;        int max_area = 0;        vector<int> height(matrix[0].size(), 0);        for (size_t i=0; i<matrix.size(); ++i) {            for (size_t j=0; j<matrix[0].size(); ++j)                if (matrix[i][j] == '0') height[j] = 0;                else ++height[j];            max_area = max(max_area, largestRectangleArea(height));        }        return max_area;    }private:    int largestRectangleArea(vector<int> &height) {        int max_area = 0, i = 0, size = height.size();        for (stack<int> stk; i<size || !stk.empty(); )            if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++);            else {                int tp = stk.top(); stk.pop();                max_area = max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1));            }        return max_area;    }};int main(int argc, char **argv){    std::vector<std::vector<char>> matrix = {            {'1', '0', '1', '0', '0'},            {'1', '0', '1', '1', '1'},            {'1', '1', '1', '1', '1'},            {'1', '0', '0', '1', '0'}    };    Solution s;    std::cout << s.maximalRectangle(matrix) << std::endl;    return 0;}

解题思路分析

0 1 0 01 1 1 00 1 1 00 0 1 00 1 0 0

对于上述这个矩阵，我们人脑是如何第一时间发现中间那坨 1 的呢？我觉得应该有下面这个过程:

           _0 1 0 0   | |_1 1 1 0   |*|*|0 1 1 0   |*|*|---------------0 0 1 00 1 0 0

首先一眼排除掉虚线下面的可能性，而上面的部分，怎么看怎么像是 [114. Largest Rectangle in Histogram](../114. Largest Rectangle in Histogram) 的图。显然如果将层数累加，则成了 height 这个 vector 了。

0 3 2 0

这就完全成了 114 题的解答了。

所以这道题比较偷懒的方法，是直接使用 114 题里的 largestRectangleArea 方法。并构建出 height 这个 vector 即可。

大部分童鞋和我一样，遇到这道题的时候，还没遇到 114, 那么灵感应该不会那么突然，常规的思路应该还是 DP。

一、力扣题解之：最长公共前缀

编写一个函数来查找字符串数组中的 最长公共前缀 。
如果不存在公共前缀，返回空字符串 ""。

示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：
0