【题目1】斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
提示：
0 <= n <= 30
【难度】简单
【解答】
方法一：动态规划
斐波那契数的边界条件是 F(0)=0 和 F(1)=1。当 n>1时，每一项的和都等于前两项的和，因此有如下递推关系：
F(n)=F(n-1)+F(n-2)
由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0)和 F(1)。
根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 O(n) 的实现。由于 F(n) 只和 F(n-1) 与 F(n-2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)。如下的代码中给出的就是这种实现。
class Solution {public int fib(int n) {if (n < 2) {return n;}int p = 0, q = 0, r = 1;for (int i = 2; i <= n; ++i) {p = q;q = r;r = p + q;}return r;}}
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
方法二：矩阵快速幂
方法一的时间复杂度是 O(n)。使用矩阵快速幂的方法可以降低时间复杂度。
首先我们可以构建这样一个递推关系：
因此：
令：
因此只要我们能快速计算矩阵 M 的 n次幂，就可以得到 F(n) 的值。如果直接求取 M^ n，时间复杂度是 O(n)，可以定义矩阵乘法，然后用快速幂算法来加速这里 M^n的求取。
class Solution {public int fib(int n) {if (n < 2) {return n;}int[][] q = {{1, 1}, {1, 0}};int[][] res = pow(q, n - 1);return res[0][0];}public int[][] pow(int[][] a, int n) {int[][] ret = {{1, 0}, {0, 1}};while (n > 0) {if ((n & 1) == 1) {ret = multiply(ret, a);}n >>= 1;a = multiply(a, a);}return ret;}public int[][] multiply(int[][] a, int[][] b) {int[][] c = new int[2][2];for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];}}return c;}}
复杂度分析
时间复杂度：O(log n)。
空间复杂度：O(1)。
方法三：通项公式
斐波那契数 F(n) 是齐次线性递推，根据递推方程 F(n)=F(n-1)+F(n-2)，可以写出这样的特征方程：
class Solution {public int fib(int n) {double sqrt5 = Math.sqrt(5);double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);return (int) Math.round(fibN / sqrt5);}}
复杂度分析
代码中使用的pow 函数的时空复杂度与 CPU 支持的指令集相关，这里不深入分析。
跳跃游戏
【题目2】给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
【难度】中等
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 3 * 10^4
0 <= nums[i] <= 10^5
【解答】
我们可以用贪心的方法解决这个问题。
设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x +nums[x]，这个值大于等于 y，即 x + nums[x]≥y，那么位置 y 也可以到达。
换句话说，对于每一个可以到达的位置 x，它使得 x+1, x+2, ⋯,x+nums[x] 这些连续的位置都可以到达。
这样以来，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置 x，如果它在最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x + nums[x] 更新 最远可以到达的位置。
在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。
以题目中的示例一
[2, 3, 1, 1, 4]为例：
我们一开始在位置 0，可以跳跃的最大长度为 2，因此最远可以到达的位置被更新为 2；
我们遍历到位置 1，由于 1 ≤2，因此位置 1 可达。我们用 11加上它可以跳跃的最大长度 3，将最远可以到达的位置更新为 4。由于 4 大于等于最后一个位置 4，因此我们直接返回 True。
我们再来看看题目中的示例二
[3, 2, 1, 0, 4]
我们一开始在位置 0，可以跳跃的最大长度为 3，因此最远可以到达的位置被更新为 3；
我们遍历到位置 1，由于 1 ≤3，因此位置 1可达，加上它可以跳跃的最大长度 2 得到 3，没有超过最远可以到达的位置；
位置 2、位置 3同理，最远可以到达的位置不会被更新；
我们遍历到位置 4，由于 4 >3，因此位置 4不可达，我们也就不考虑它可以跳跃的最大长度了。
在遍历完成之后，位置 4仍然不可达，因此我们返回 False。
public class Solution {public boolean canJump(int[] nums) {int n = nums.length;int rightmost = 0;for (int i = 0; i < n; ++i) {if (i <= rightmost) {rightmost = Math.max(rightmost, i + nums[i]);if (rightmost >= n - 1) {return true;}}}return false;}}
复杂度分析
时间复杂度：O(n)，其中 n为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。
空间复杂度：O(1)，不需要额外的空间开销。
最大矩形
【题目3】给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix=[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = []
输出：0
示例 3：
输入：matrix = [["0"]]
输出：0
示例 4：
输入：matrix = [["1"]]
输出：1
示例 5：
输入：matrix = [["0","0"]]
输出：0
提示：
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'
【难度】难
【解答】
方法一:
我们首先计算出矩阵的每个元素的左边连续 1的数量，使用二维数组 left 记录，其中 left[i][j] 为矩阵第 i行第 j列元素的左边连续 1 的数量。
随后，对于矩阵中任意一个点，我们枚举以该点为右下角的全 1 矩形。
具体而言，当考察以matrix[i][j] 为右下角的矩形时，我们枚举满足 0≤k≤i 的所有可能的 k，此时矩阵的最大宽度就为left[i][j],left[i−1][j],…,left[k][j]的最小值。
代码
class Solution {public int maximalRectangle(char[][] matrix) {int m = matrix.length;if (m == 0) {return 0;}int n = matrix[0].length;int[][] left = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == '1') {left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;}}}int ret = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == '0') {continue;}int width = left[i][j];int area = width;for (int k = i - 1; k >= 0; k--) {width = Math.min(width, left[k][j]);area = Math.max(area, (i - k + 1) * width);}ret = Math.max(ret, area);}}return ret;}}
复杂度分析
时间复杂度：O(m^2n)，其中 m和 n分别是矩阵的行数和列数。计算 left 矩阵需要 O(mn)的时间。随后对于矩阵的每个点，需要 O(m) 的时间枚举高度。故总的时间复杂度为O(mn)+O(mn)⋅O(m)=O(m^2n)。
空间复杂度：O(mn)，其中 m 和 n分别是矩阵的行数和列数。我们分配了一个与给定矩阵等大的数组，用于存储每个元素的左边连续 1的数量。
方法二：单调栈
class Solution {public int maximalRectangle(char[][] matrix) {int m = matrix.length;if (m == 0) {return 0;}int n = matrix[0].length;int[][] left = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == '1') {left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;}}}int ret = 0;for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法int[] up = new int[m];int[] down = new int[m];Deque<Integer> stack = new LinkedList<Integer>();for (int i = 0; i < m; i++) {while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {stack.pop();}up[i] = stack.isEmpty() ? -1 : stack.peek();stack.push(i);}stack.clear();for (int i = m - 1; i >= 0; i--) {while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {stack.pop();}down[i] = stack.isEmpty() ? m : stack.peek();stack.push(i);}for (int i = 0; i < m; i++) {int height = down[i] - up[i] - 1;int area = height * left[i][j];ret = Math.max(ret, area);}}return ret;}}
复杂度分析
时间复杂度：O(mn)，其中m和n分别是矩阵的行数和列数。计算 left 矩阵需要 O(mn)的时间；对每一列应用柱状图算法需要 O(m)的时间，一共需要 O(mn)的时间。
空间复杂度：O(mn)，其中 m和 n分别是矩阵的行数和列数。我们分配了一个与给定矩阵等大的数组，用于存储每个元素的左边连续1的数量。
原文作者：IT枫斗者；如有侵权，请联系管理员删除。
