年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容）
QQ交流群：606939954
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
实例1：直方图装水
实例2：两不相交子数组最大和
实例3：左边部分最大值减右边部分最大值得到的绝对值最大多少？
实例1：直方图装水
给定一个数组,每个位置的值代表一个高度。那么整个数组可以看过是一个直方图。
如果把这个直方图当做容器的话,求这个容器能装多少水。例如:
3, 1, 2,4
代表第一个位置高度为3,
第二个位置高度为1,
第三个位置高度为2,
第四个位置高度为4
3,1, 2,4这个数组代表的容器可以装3格的水。
思路：
每次只求取当前位置 i ，能装入多少水，不管其他地方。
具体条件，为了理解方便，假设当前位置是凹位置，即两边高，一定可以装水
1、当前位置 i
2、0 ~ i-1 位置最大值
3、i+1 到 N-1 位置最大值
那么当前位置的可以装入的水量就是 maxLeft - arr[i]
怎么求取当前位置的装水量已经解决，但是有一个问题需要解决，也是决定着当前算法时间复杂度和空间复杂度的最重要的影响因素。如何求得两边的最大值？
第一种：暴力求解
1、当前位置 i
2、遍历求解 0 ~ i-1 位置最大值
3、遍历求解 i+1 到 N-1 位置最大值
时间复杂度 O(N^2)
第二种：预处理数组
例如数组
3 1 2 4 1 5 4 6 2
先从左向右遍历求得每一个位置上的最大值
那么每一个 i的 0 ~ i-1 位置最大值就是arr[i-1]
3 3 3 4 4 5 5 6 6
再从右向左遍历求得每一个位置上的最大值
那么每一个 i的i+1 到 N-1 位置最大值就是arr[i+1]
2 6 6 6 6 6 6 6 6
这样每次找到maxL maxR 的时间复杂度就是 O(1)
总时间复杂度 O(N)
第三种：双指针外排
我们知道无论这个直方图是怎么样的，两端是不可能装水的。
情况一：maxL <= maxR
情况二：maxL > maxR
1_1_双指针外排.png
/**
* @description: 直方图装水问题
*/
public class Code_10_WaterProblem {
// 暴力求解
public static int getWater1(int[] arr) {
if (arr == null || arr.length < 3) { // 只有两端是无法进行装水的
return 0;
}
int value = 0;
for (int i = 1; i < arr.length - 1; i++) {
int maxLeft = 0;
int maxRight = 0;
for (int j = 0; j < i; j++) {
maxLeft = Math.max(maxLeft, arr[j]);
}
for (int j = i + 1; j < arr.length; j++) {
maxRight = Math.max(maxRight, arr[j]);
}
value += Math.max(0, Math.min(maxLeft, maxRight) - arr[i]);
}
return value;
}
// 预处理数组
public static int getWater2(int[] arr) {
if (arr == null || arr.length < 3) {
return 0;
}
int n = arr.length - 2; // 左右两端就是当前最大，不需要求
int[] maxLefts = new int[n]; // 左边最大预处理数组
int[] maxRights = new int[n]; // 右边最大预处理数组
// 初始化
maxLefts[0] = arr[0]; // 左端
maxRights[n - 1] = arr[arr.length - 1]; // 右端
for (int i = 1; i < n; i++) {
maxLefts[i] = Math.max(maxLefts[i - 1], arr[i]);
}
for (int i = n - 2; i >= 0; i--) {
maxRights[i] = Math.max(maxRights[i + 1], arr[i + 2]);
}
int value = 0;
for (int i = 1; i <= n; i++) {
value += Math.max(0, Math.min(maxLefts[i - 1], maxRights[i - 1]) - arr[i]);
}
return value;
}
// 预处理数组，省去一个数组，只需要右预处理数组
public static int getWater3(int[] arr) {
if (arr == null || arr.length < 3) {
return 0;
}
int n = arr.length - 2;
int[] maxRights = new int[n];
maxRights[n - 1] = arr[n + 1];
for (int i = n - 2; i >= 0; i--) {
maxRights[i] = Math.max(maxRights[i + 1], arr[i + 2]);
}
int maxLeft = arr[0];
int value = 0;
for (int i = 1; i <= n; i++) {
value += Math.max(0, Math.min(maxLeft, maxRights[i - 1]) - arr[i]);
maxLeft = Math.max(maxLeft, arr[i]);
}
return value;
}
// 双指针 O(1) 空间复杂度 O(N) 时间复杂度
public static int getWater4(int[] arr) {
if (arr == null || arr.length < 3) {
return 0;
}
int value = 0;
// 双指针
int L = 1;
int R = arr.length - 2;
int maxL = arr[0];
int maxR = arr[arr.length - 1];
while (L <= R) {
if (maxL <= maxR) {
value += Math.max(0, maxL - arr[L]);
maxL = Math.max(maxL, arr[L++]);
} else {
value += Math.max(0, maxR - arr[R]);
maxR = Math.max(maxR, arr[R--]);
}
}
return value;
}
// for test
public static int[] generateRandomArr() {
int[] arr = new int[(int) (Math.random() * 98) + 2]; // 产生0 ~ 100中长度至少为3的随机数组
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 200) + 2;
}
return arr;
}
public static void main(String[] args) {
for (int i = 0; i < 2; i++) {
int[] arr = generateRandomArr();
// int[] arr = {9,1,2,6,4};
int val1 = getWater1(arr);
int val2 = getWater2(arr);
int val3 = getWater3(arr);
int val4 = getWater4(arr);
if (val1 != val2 || val3 != val4 || val1 != val3) {
System.out.println("算法出错 start");
System.out.println("val1=" + val1 + " val2=" + val2 + " val3=" + val3 + " val4=" + val4);
System.out.println("算法出错 end");
}
}
}
}
实例2：两不相交子数组最大和
给定一个数组,长度大于2,找出不相交的两个子数组,情况是很多的。请返回这么多情况中,两个不相交子数组最大的和。例如:
-1, 3, 4,-9, 1, 2
当两个不相交子数组为[3, 4]和[1, 2]时,可以得到最大的和为10.
思路：
用到了前面讲到的，单一求一个数组的子数组最大和
https://www.jianshu.com/p/a1ce2907220e 中实例3
过程一样，唯一的变化是反向求解一下子数组最大和。
需要做到的目标是：
对于数组中的任意元素 i， 以i 为分割点，
可以获取到 0 ~ i 范围内子数组最大和，
同时可以获取到 i+1 ~ N-1 范围内的子数组最大和
那么以 i 为分割点的两个不相交子数组和就能得到。
1、准备一个辅助数组，用来存储 i ~ N-1 位置的子数组最大和
2、第一次遍历，求取 i 到 N-1 范围内最大子数组和
3、第二次遍历，求取 0 到 i 范围内最大子数组和
同时 取 i+1 到 N-1 范围内最大子数组和进行累加比较
public class Code_11_TwoSubArrayMaxSum {
public static int twoSubArrMaxSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
// 每一项存 i 到 N-1 范围内最大子数组和
int[] maxRight = new int[arr.length];
int max = Integer.MIN_VALUE;
int cur = 0;
// 第一次遍历，求取 i 到 N-1 范围内最大子数组和
for (int i = arr.length - 1; i > 0; i--) { // i==0 不需要进行求最大累加和
cur += arr[i];
max = Math.max(cur, max);
maxRight[i] = max; // 入数组存储
cur = cur < 0 ? 0 : cur;
}
max = Integer.MIN_VALUE;
int res = Integer.MIN_VALUE;
cur = 0;
// 第二次遍历，求取 0 到 i 范围内最大子数组和
// 同时 取 i+1 到 N-1 范围内最大子数组和进行累加比较
for (int i = 0; i < arr.length - 1; i++) {
cur += arr[i];
max = Math.max(max, cur);
res = Math.max(res, max + maxRight[i + 1]);
cur = cur < 0 ? 0 : cur;
}
return res;
}
// for test 暴力求解
public static int rightAnswer(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int res = Integer.MIN_VALUE;
for (int p = 0; p < arr.length - 1; p++) {
res = Math.max(res, maxSum(arr, 0, p) + maxSum(arr, p + 1, arr.length - 1));
}
return res;
}
// for test
public static int maxSum(int[] arr, int l, int r) {
int max = Integer.MIN_VALUE;
int cur = 0;
for (int i = l; i <= r; i++) {
cur += arr[i];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
return max;
}
// for test
public static int[] generateRandomArray() {
int[] res = new int[(int) (Math.random() * 10) + 1];
for (int i = 0; i < res.length; i++) {
res[i] = (int) (Math.random() * 20) - 10;
}
return res;
}
// for test
public static void main(String[] args) {
int testTime = 50;
boolean hasErr = false;
for (int i = 0; i < testTime; i++) {
int[] test = generateRandomArray();
if (twoSubArrMaxSum(test) != rightAnswer(test)) {
hasErr = true;
}
}
if (hasErr) {
System.out.println("出错");
} else {
System.out.println("一切OK");
}
}
}
实例3：左边部分最大值减右边部分最大值得到的绝对值最大多少？
给定一个长度为N (N>1)的整型数组arr,可以划分成左右两个部分,
左部分为arr [0..K],右部分为arr [K+1..N-1], K可以取直的范围是[0, N-2]。
求这么多划分方案中,左部分中的最大值减去右部分最大值的绝对值中,最大是多少?
列如: [2, 7, 3, 1, 1],当左部分为[2,7],右部分为[3, 1, 1]时,左部分中的最大值减去右部分最大值的绝对值为4。
当左部分为 [2,7, 3],右部分为[1,1]时,左部分中的最大值减去右部分最大值的绝对值为6。
还有很多划分方案,但最终返回6。
思路：
1、利用预处理数组
2、最优解:数学思维跳跃
思路1：预处理数组
使用两个数组分别记录 0~i 上的最大值，和i+1 ~ N-1范围的最大值。这样就可以随时取出任意i 位置为划分时，两边的最大值。如
2 7 3 1 6
2 7 7 7 7 ---> 0~i 范围最大值
7 7 6 6 6 ---> i+1~N-1 范围最大值
任意 i ，如i=0为划分，将数组划分为两个部分
maxL从 0 ~ i 范围取最大值为2
maxR从 i+1 ~ N-1 范围取最大值为 7
|2-7|=5
思路2：思维跳跃
这是一个凭经验的思维跳跃解法。
1、先遍历一遍数组，找到数组的最大值max。
2、将max分别划分到左右两个部分进行考虑
当max划分到左边部分。
3_1_max在左边部分.png
回头看看题意：左边部分最大值-右边部分最大值。
现在全局最大值在左边部分，并且需要右边部分找一个最大值
res=max-右边部分最大值maxR
想要res 尽可能的大，那么右边部分的最大值就要尽可能的小，什么时候maxR 尽可能的小呢？答案是 maxR=arr[N-1] 即最后一个元素时最小。
举个栗子：
5 2 9 2 3 5 4
现在max=9 划分到了左边，那么maxR=4是右边部分最大值中较小的。只有一个元素就是最小的，如果多纳入元素，最大值可能就会变大，如纳入5之后，最大值就变成了5而不是4
同理max划分在右边部分
左边部分最大值尽可能的小，那么就是第一个元素arr[0]
public class Code_12_MaxABSBetweenLeftAndRight {
// 预处理数组
public static int maxABS1(int[] arr) {
int[] maxL = new int[arr.length];
int[] maxR = new int[arr.length];
// 左 -- > max
maxL[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
maxL[i] = Math.max(maxL[i - 1], arr[i]);
}
// 右 --> max
maxR[arr.length - 1] = arr[arr.length - 1];
for (int i = arr.length - 2; i >= 0 ; i--) {
maxR[i] = Math.max(maxR[i+1], arr[i]);
}
int res = 0;
for (int i = 0; i < arr.length - 1; i++) {
res = Math.max(res, Math.abs(maxL[i] - maxR[i+1]));
}
return res;
}
public static int maxABS2(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max);
}
return Math.abs(max - Math.min(arr[0], arr[arr.length - 1]));
}
public static int[] generateRandomArray(int length) {
int[] arr = new int[length];
for (int i = 0; i != arr.length; i++) {
arr[i] = (int) (Math.random() * 1000) - 499;
}
return arr;
}
public static void main(String[] args) {
int[] arr = generateRandomArray(200);
System.out.println(maxABS1(arr));
System.out.println(maxABS2(arr));
}
}
网友评论