Leetcode 215：数组中的第K个最大元素

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2：
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解题思路

偷了个懒，就是利用求第k个小的数字改的。因为求第k个大的数字和求第m个小的数字有以下关系（假设数组长度为len）：m=len-k+1，所以直接进行转换即可。

代码实现

复杂度分析

时间复杂度：O(nlogn)

Leetcode 221：最大正方形

题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例

输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

解题思路

参考官方题解，步骤如下：

1. 我们用 0 初始化另一个矩阵 dp，维数和原始矩阵维数相同；dp(i,j) 表示的是由 1 组成的最大正方形的边长。
2. 从 (0,0)(0,0) 开始，对原始矩阵中的每一个 1，我们将当前元素的值更新为

dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1

3. 我们用一个变量记录当前出现的最大边长，这样遍历一次就可以找到正方形的最大边长maxr，返回的结果就是maxr*maxr。

由于动态规划可以分解为若干个独立的子问题，由于一个格子的值受其左侧、左上角和上侧三个点来决定，所以我们以四个格子举例来解释这个式子，如下图所示。我们假设左下角的格子为最小值，那么有三种情况：

1. 该值为0。则和前面组不成正方形，dp[i]=0+1=1。
2. 该值为1。则其它值只能大于等于1，若都是等于1，说明周围三个小正方形没办法和其它正方形组成更大的正方形，所以只能它们4个组成。
3. 该值为大于1的数，假设为2。则代表该蓝色格子与其左侧、左上侧、上侧组成了一个边长为2的正方形，由于黑色和绿色都大于2，所以黑色格子的左上角和上侧、绿色格子的上侧都不是0，于是就可以组成一个3*3的正方形，也即边长=2+1=3。其它大小以此类推。

上面的时间复杂度为O(mn)，空间复杂度为O(mn)。接下来，我们可以对其进行优化。在上面的方法中，计算第i行的dp只用到了上一个元素和第i-1行，因此我们可以使用一维dp来满足要求。在扫描一行原始矩阵元素的时候，根据公式dp[j]=min(dp[j−1],dp[j],prev)来更新dp，其中prev是dp[j-1]。对于每一行，我们执行一遍过程，最后输出最大值即可。新的方法时间复杂度为O(mn)，空间复杂度为O(n)。

代码实现

复杂度分析

时间复杂度为O(mn)，空间复杂度为O(n)。