目录

45、跳跃计划

53、最大子数组和

55、跳跃游戏

62、不同路径

 63、不同路径2

 64、最小路径和

 70、爬楼梯

 72、编辑距离

84、柱形图中最大的矩形

85、最大矩形

 4721、排队

45、跳跃计划

当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。

思路虽然是这样，但在写代码的时候还不能真的就能跳多远跳远，那样就不知道下一步最远能跳到哪里了。

所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

class Solution {public int jump(int[] nums) {int next = 0;int ans = 0;int end = 0;int n = nums.length;for (int i = 0; i < n - 1; i ++) {next = Math.max(next,nums[i] + i);if (i == end) {ans ++;end = next;}}return ans;}
}

53、最大子数组和

贪心思路：当我们连续子段和是负数时，我们是没必要留给下一个数的，因为下一个数不要这一段的和肯定更大，因此我们发现如果sum已经小于0了，我们就留给下一段一个0，每次更新最大值就行

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int res = Integer.MIN_VALUE;for (int i = 0,sum = 0; i < n; i ++) {sum += nums[i];res = Math.max(res,sum);if (sum < 0) sum = 0;}return res;}
}

动态规划：f[i] 表示nums中以i结尾的区间中最大和，f[i] 可以拆分为长度为1和长度大于1的区间，那么我们可以得到 f[i] 可以由 nums[i] 或者 f[i - 1] + nums[i]转移，两边取掉 nums[i],那就成了 nums[i - 1] + max(f[i - 1],0)，我们每次遇到的都是 f[i - 1] ，因此可以用 last 来替换！

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int res = Integer.MIN_VALUE;int last = 0;for (int i = 0; i < n; i ++) {last = Math.max(last,0) + nums[i];res = Math.max(res,last);}return res;}
}

55、跳跃游戏

 思路：暴力解法,记录我们可以到达的最远的点，如果我们到达了最远的点还不能到终点，就返回false ，否则返回true

class Solution {public boolean canJump(int[] nums) {int n = nums.length;int end = 0;for (int i = 0; i < n; i ++) {end = Math.max(end,nums[i] + i);if (i == end && i != n - 1) return false; }return true;}
}

62、不同路径

动态规划模板题，任何学动态规划的童鞋都不能没做过这道题！！！！

想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。

此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。

那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。

class Solution {public int uniquePaths(int m, int n) {int[] f = new int[n];for (int i = 0; i < m; i ++) {for (int j = 0; j < n; j ++) {if (i == 0 && j == 0) f[j] = 1;else if (j > 0) {f[j] += f[j - 1];}}}return f[n - 1];}
}

加了维度压缩，因为是有一层是上一层转移,j 没变，但我记得比赛时候这题有可能爆int。。。。。

 63、不同路径2

 思路：一模一样，如果当前格子不是障碍物，它才有所谓的路径数量

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int n = obstacleGrid.length;int m = obstacleGrid[0].length;int[][] f = new int[n][m];for (int i = 0; i < n; i ++) {for (int j = 0; j < m; j ++) {if (obstacleGrid[i][j] == 0) {if (i == 0 && j == 0) f[i][j] = 1;else {if (i > 0) f[i][j] += f[i - 1][j];if (j > 0) f[i][j] += f[i][j - 1];}}}}return f[n - 1][m - 1];}
}

 64、最小路径和

 思路：这三道题转移方程其实都是一样的，这道题唯一不同的点在于我们求得是最小值，不能让默认初始化为0干扰我们最终答案，因此我们初始化为无穷即可

class Solution {public int minPathSum(int[][] grid) {int n = grid.length;int m= grid[0].length;int[][] f = new int[n][m];for (int i = 0; i < n; i ++) Arrays.fill(f[i],0x3f3f3f3f);f[0][0] = grid[0][0];for (int i = 0; i < n; i ++) {for (int j = 0; j < m; j ++) {if (i > 0) f[i][j] = Math.min(f[i][j],f[i - 1][j] + grid[i][j]);if (j > 0) f[i][j] = Math.min(f[i][j],f[i][j - 1] + grid[i][j]);}}return f[n - 1][m - 1];}
}

 70、爬楼梯

 思路：同样的，我们f【i】可以由它的前一个（i - 1）跳一步或者 i - 2 （跳两步）得来，累加即可

class Solution {public int climbStairs(int n) {if (n == 0 || n == 1) return 1;int[] f = new int[n + 1];f[0] = 1;f[1] = 1;for (int i = 2 ; i <= n; i ++) {f[i] += f[i - 1] + f[i - 2];}return f[n];}
}

我们为了省空间可以用a,b来代替

class Solution {public int climbStairs(int n) {if (n == 0 || n == 1) return 1;int[] f = new int[n + 1];int a = 1;int b = 1;for (int i = 2 ; i <= n; i ++) {int c = a + b;a = b;b = c;}return b;}
}

 72、编辑距离

转移方程如上图所示，初始化记得我们每一个有意义字符串对应另一个字符串为0时的值应该时 有意义字符串的长度（删）

class Solution {public int minDistance(String word1, String word2) {int n = word1.length();int m = word2.length();word1 = " " + word1;word2 = " " + word2;int[][] f = new int[n + 1][m + 1];// for (int i = 0; i <= n; i ++) Arrays.fill(f[i],0x3f3f3f3f);for (int i = 1; i <= n; i ++) f[i][0] = i;for (int j = 1; j <= m; j ++) f[0][j] = j;for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m; j ++) {f[i][j] = Math.min(f[i - 1][j],f[i][j - 1]) + 1;f[i][j] = Math.min(f[i][j],f[i - 1][j - 1] + (word1.charAt(i) == word2.charAt(j) ? 0 : 1));}}return f[n][m];}
}

为什么这里可以去掉初始化，因为我们更新最大值时没有用到它未更新时的状态，因此动态规划依然按照拓扑序

84、柱形图中最大的矩形

1、 此题的本质是找到每个柱形条左边和右边最近的比自己低的矩形条，然后用宽度乘上当前柱形条的高度作为备选答案。
2、解决此类问题的经典做法是单调栈，维护一个单调递增的栈，如果当前柱形条 i 的高度比栈顶要低，则栈顶元素 cur 出栈。出栈后，cur 右边第一个比它低的柱形条就是 i，左边第一个比它低的柱形条是当前栈中的 top。不断出栈直到栈为空或者柱形条 i 不再比 top 低。
3、满足 2 之后，当前矩形条 i 进栈。

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;Stack stk = new Stack<>();int[] l = new int[n];int[] r = new int[n];for (int i = 0; i < n; i ++) {while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) stk.pop();if (stk.isEmpty()) l[i] = -1;else l[i] = stk.peek();stk.push(i);}stk.clear();for (int i = n - 1; i >= 0; i --) {while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) stk.pop();if (stk.isEmpty()) r[i] = n;else r[i] = stk.peek();stk.push(i);}int res = 0;for (int i = 0; i < n; i ++) {res = Math.max(res,(r[i] - l[i] - 1) * heights[i]);}return res;}
}

85、最大矩形

(单调栈) O(nm)O(nm)
1、将 Largest Rectangle in Histogram 问题扩展到二维。
2、一行一行考虑，类比 Largest Rectangle in Histogram，一行内所有柱形条的高度 heights 就是当前 (i, j) 位置能往上延伸的最大高度。
3、直接套用 Largest Rectangle in Histogram 的单调栈算法即可。

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;Stack stk = new Stack<>();int[] l = new int[n];int[] r = new int[n];for (int i = 0; i < n; i ++) {while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) stk.pop();if (stk.isEmpty()) l[i] = -1;else l[i] = stk.peek();stk.push(i);}stk.clear();for (int i = n - 1; i >= 0; i --) {while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) stk.pop();if (stk.isEmpty()) r[i] = n;else r[i] = stk.peek();stk.push(i);}int res = 0;for (int i = 0; i < n; i ++) {res = Math.max(res,(r[i] - l[i] - 1) * heights[i]);}return res;}public int maximalRectangle(char[][] matrix) {int n = matrix.length;int m = matrix[0].length;int[][] f = new int[n][m];for (int i = 0; i < n; i ++) {for (int j = 0; j < m; j ++) {if (matrix[i][j] == '1') {if (i == 0) f[i][j] = 1;else f[i][j] = 1 + f[i - 1][j];}}}int res = 0;for (int i = 0; i < n; i ++) res = Math.max(res,largestRectangleArea(f[i]));return res;}
}

 4721、排队

这道题是单调栈加二分的经典题目，以往的单调栈最常用是求我们最靠近且最小（大）的值，而本题中求的是；最远最小的值，因此我们要改变单调栈的添加顺序，从后往前，试想：如果存在一个靠左的数比靠右的数还大，那它是没有必要存在栈中的，因此栈中一定是从大到小的顺序，因此我们可以对每一个元素二分求小于它的数里边最大的一个

import java.util.*;public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] h = new int[n];for (int i = 0; i < n; i ++) h[i] = sc.nextInt();int top = 0;int[] stk = new int[n + 10];int[] res = new int[n];for (int i = n - 1; i >= 0; i --) {if (top == 0 || h[stk[top - 1]] >= h[i]) res[i] = -1;else {int l = 0;int r = top - 1;while (l < r) {int mid = l + r >> 1;if (h[stk[mid]] < h[i]) r = mid;else l = mid + 1;}res[i] = stk[r] - i - 1;}if (top == 0 || h[i] < h[stk[top - 1]]) stk[top ++] = i;}for (int i = 0; i < n; i ++) {System.out.print(res[i] + " ");}}
}