02-递归逆序栈-小和问题-子数组最大和-小B首都防卫工作
年轻即出发...
简书：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：子数组最大和
实例4：小B首都防卫工作
实例1：递归逆序栈
一个栈依次压入1、2、3、4、5,那么从栈顶到栈底分别为5、4、 3、2、1,将这个栈转置后,从栈顶到栈底为1、2、3、4、5,也就是实现栈中元素的逆序,但是只能用递归函数来实现,不能用其他数据结构。
递归函数：删除并返回栈底元素
1、弹出栈顶元素
2、当前栈为空吗 ？return 栈顶元素
3、继续递归 ---> 等栈底元素
4、回写栈顶元素到 stack
5、return 栈底元素;
1_1_递归去栈底元素.png
递归函数：逆序栈
1_2_递归实现栈逆序.png
import java.util.Stack;
/**
* @description: 递归逆序栈
* @version: 1.0
*/
public class Code_05_ReverseStackByRecur {
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) return;
int lastElement = getAndRemoveLastElement(stack);
reverse(stack);
stack.push(lastElement); // 回写
}
// 获取并删除栈底元素,其他元素保持不变
public static int getAndRemoveLastElement(Stack<Integer> stack) {
Integer res = stack.pop();
if (stack.isEmpty()) {
return res;
} else {
int lastElement = getAndRemoveLastElement(stack);
stack.push(res);
return lastElement;
}
}
public static void main(String[] args) {
Stack<Integer> test = new Stack<>();
test.push(1);
test.push(2);
test.push(3);
reverse(test);
while (!test.isEmpty()) {
System.out.println(test.pop());
}
}
}
实例2：小和问题（归并排序的变形）
数组小和的定义如下:
例如,数组s=[1, 3, 5, 2, 4, 6],
在s[0]的左边小于或等于s[0]的数的和为0,
在s[1]的左边小于或等于s[1]的数的和为1,
在s [2]的左边小于或等于s[2]的数的和为1+3-4,
在s[3]的左边小于或等于s[3的数的和为1,
在s[4]的左边小于或等于s[4]的数的和为1+3+2-6,
在s[5]的左边小于或等于s[5]的数的和为 1+3+5+2+4-15,
所以s的小和为0+1+4+1+6+15-27.给定一个数组s,实现函数返回s的小和。
/**
* @description: 小和问题
* 改写归并排序即可
*
* 数组小和的定义如下:
*
* 例如,数组s=[1, 3, 5, 2, 4, 6],
*
* 在s[0]的左边小于或等于s[0]的数的和为0,
*
* 在s[1]的左边小于或等于s[1]的数的和为1,
*
* 在s [2]的左边小于或等于s[2]的数的和为1+3-4,
*
* 在s[3]的左边小于或等于s[3的数的和为1,
*
* 在s[4]的左边小于或等于s[4]的数的和为1+3+2-6,
*
* 在s[5]的左边小于或等于s[5]的数的和为 1+3+5+2+4-15,
*
*
* 所以s的小和为0+1+4+1+6+15-27.给定一个数组s,实现函数返回s的小和。
*/
public class Code_06_SmallSum {
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) return 0;
return mergesort(arr, 0, arr.length - 1);
}
public static int mergesort(int[] arr, int L, int R) {
if (L == R) return 0;
int mid = L + ((R - L) >> 1);
return mergesort(arr, L, mid) +
mergesort(arr, mid + 1, R) +
merge(arr, L, mid, R);
}
public static int merge(int[] arr, int L, int mid, int R) {
if (L == R) {
return 0;
}
int[] help = new int[R - L + 1];
int i = 0;
int smallSum = 0;
int p1 = L; // 双指针外排方式排序
int p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
smallSum = arr[p1] <= arr[p2] ? arr[p1] * (R - p2 + 1) : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
for (i = 0; i < help.length; i++)
arr[L + i] = help[i];
return smallSum;
}
public static void main(String[] args) {
int[] arr = {4, 2, 5, 7};
System.out.println(smallSum(arr));
}
}
实例3：最大累加和
给定一个数组arr,返回子数组的最大累加和。例如, arr=[1,-2, 3,5,-2,6,-1],所有的子数组中, [3, 5,-2,6]可以累加出最大的和12,所以返回12.
思路
一个arr 中存在整数，那么这个arr 的最大累加和的子数组一定不是以负数开头的。
3_1_数组中有整数.png
如：
arr = {-1, -2, -3, 4 -1, 5, -1, -7}
tmpArr = {4 , -1, 5}
tmpArr一定不会以-3 开头，cur，的存在就是为了排除这种问题，遇到这种问题就抛弃归0；
cur ：抛弃所有以负数开头的最大子数组的问题
/**
* @description: 子数组的最大累加和
* 给定一个数组arr,返回子数组的最大累加和。
* 例如, arr=[1,-2, 3,5,-2,6,-1],所有的子数组中,
* [3, 5,-2,6]可以累加出最大的和12,所以返回12.
* @version: 1.0
*/
public class Code_06_SubArrayMaxSum {
public static int maxSubArr(int[] arr) {
if (arr == null || arr.length == 0)return 0;
int max = Integer.MIN_VALUE;
int cur = 0;
for (int i = 0; i < arr.length; i++) {
cur += arr[i];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
return max;
}
public static void main(String[] args) {
int[] arr = {-1,1,2,-8,12,1,-3,-4,6};
System.out.println(maxSubArr(arr));
}
}
实例4：小B首都防卫工作
小B负责首都的防卫工作。
首都处于一个四面环山的盆地中,周围的n个小山构成一个环,作为预警措施,小B计划在每个小山上设置一个观察哨, 日夜不停的瞭望周围发生的情况。一旦发生外敌入侵事件,山顶上的岗哨将点燃烽烟。
若两个岗哨所在的山峰之间的那些山峰,高度都不大于这两座山峰,且这两个山峰之间有相连通路,则岗哨可以观察到另一个山峰上的烽烟是否点燃。
由于小山处于环上,任意两个小山之间存在两个不同的连接通路。
满足上述不遮挡的条件下,一座山峰上岗哨点燃的烽烟至少可以通过一条通路被另一端观察到。
对于任意相邻的岗哨,一端的岗哨一定可以发现一端点燃的烽烟。
小B设计的这种保卫方案的一个重要特性是能够观测到对方烽烟的岗哨对的数量,她希望你能够帮她解决这个问题。
输入中有多组测试数据。
每组测试数据的第一行为一个整数n (3<=n<=10~6) ,为首都周围的小山数量,第二行为n个整数,依次表示小山的高度h, (1<=h<=10'9)
输出对每组测试数据,在单独的一行中输出能相互观察到的岗哨的对数。
样例
输入 512453样例
输出 7
思路：
1、假设所有的高度都是不重复的 5 3 0 7 1 4
最大7，次大5，那么任意介于 7和5 之间的数向大找数，总能找到两对
4：5 7
1：4 7
3：5 7
2：3 7
注意：向大找如 4 就是 (4, 5) (4, 7) 而不是找(7, 4)
4_1_任意一个介于最大和次大数之间形成的对数.png
2、对于任意相邻的岗哨,一端的岗哨一定可以发现一端点燃的烽烟。
说明：任意两个山峰可以互相看到
那么对于通高度的也是一样。
2 2 2 2 互相看见对数
4_2_任意连续相同高度之间对数.png
// 根据一个元素当前在栈中出现的次数，算出本身存在的对数
// 如 2 2 2 是 3 对 C(3,2)
public static long getInternalSum(int times) {
return times == 1 ? 0L : (long) times * (long) (times - 1) / 2L;
}
3、对于数组元素，进行依次压栈，重复元素记录次数+1即可，入栈元素数据结构
// 数据结构化处理
public static class Pair {
public int value; // 元素值
public int times; // 元素在数组中出现的次数
public Pair(int value) {
this.value = value;
}
}
4、找到数据中的最大数，从对大数开始压栈
int maxIndex = 0;
for (int i = 0; i < arr.length; i++) { // 找打最大数
maxIndex = arr[maxIndex] < arr[i] ? maxIndex = i : maxIndex;
}
int value = arr[maxIndex];
Stack<Pair> stack = new Stack<>();
stack.push(new Pair(value));
5、由于是从最大数开始进行的压栈，山峰又是环形，需要知道每次入栈的元素下标
5 3 1 2 4 6
如最大是6 ，6 的下标是5，
那么下一个入栈的元素下标nextIndex = 0，即arr[0] = 5
/**
* 返回下一个元素的下标 3 5 1 环形结构，1 的下一个数3 的下标 0
*
* @param size 数组长度
* @param i 当前下标
* @return 下一个下标
*/
public static int nextIndex(int size, int i) {
return i < (size - 1) ? i + 1 : 0;
}
处理各种情况
一般情况
1、m==d d 次数+1
2、m < d m 入栈
3、m > d
d 弹出栈， 计算自己构成的对数 + 和自己的下一位 b 以及新来的 m 构成的对数
while (index != maxIndex) { // 数组循环，存在元素
value = arr[index];
while (!stack.isEmpty() && stack.peek().value < value) { // 大于
int times = stack.pop().times; // 在栈中已经存在的次数
long internalSum = getInternalSum(times); // 同数组成的对数
// 栈中数 5 222 来了value=3 对数=222组成的对数 + 222 分别同 5 和 3 组成的对数（times * 2）
res += internalSum + times * 2;
}
if (!stack.isEmpty() && stack.peek().value == value) { // 等于
stack.peek().times++;
} else { // 小于 ，入栈
stack.push(new Pair(value));
}
index = nextIndex(size, index);
}
另一种情况，数组入栈完毕，但是栈中还有余数未弹出
while (!stack.isEmpty()) { // 经过上述过程，数组元素遍历完毕，但是栈中还有元素
int times = stack.pop().times;
res += getInternalSum(times);
if (!stack.isEmpty()) { // 排除是最后栈底元素情况
res += times; // 先加一个方向和下一个数的对数
if (stack.size() > 1) { // 不是最后两位数
res += times;
} else {
res += stack.peek().times > 1 ? times : 0; // 栈底元素只有入一次栈
// 5 222 2只能向一个方向找到5，另一个方向找到的是同一个5，不需要。
}
}
}
所有代码
import java.util.Stack;
/**
* @description: 小B首都防卫工作
* @version: 1.0
*/
public class Code_07_MountainsAndFlames {
// 数据结构化处理
public static class Pair {
public int value; // 元素值
public int times; // 元素在数组中出现的次数
public Pair(int value) {
this.value = value;
}
}
// 根据一个元素当前在栈中出现的次数，算出本身存在的对数
// 如 2 2 2 是 3 对 C(3,2)
public static long getInternalSum(int times) {
return times == 1 ? 0L : (long) times * (long) (times - 1) / 2L;
}
/**
* 返回下一个元素的下标 3 5 1 环形结构，1 的下一个数3 的下标 0
*
* @param size 数组长度
* @param i 当前下标
* @return 下一个下标
*/
public static int nextIndex(int size, int i) {
return i < (size - 1) ? i + 1 : 0;
}
/**
* 第一步：找到最大值
* 第二步：以最大值开始进行遍历入栈
* 依次入栈并处理对数
* 第三步：栈中剩余的元素对数
*/
public static long communications(int[] arr) {
if (arr == null || arr.length < 2) return 0;
int maxIndex = 0;
for (int i = 0; i < arr.length; i++) { // 找打最大数
maxIndex = arr[maxIndex] < arr[i] ? maxIndex = i : maxIndex;
}
int value = arr[maxIndex];
Stack<Pair> stack = new Stack<>();
stack.push(new Pair(value));
int size = arr.length;
int index = nextIndex(size, maxIndex);
long res = 0L;
while (index != maxIndex) { // 数组循环，存在元素
value = arr[index];
while (!stack.isEmpty() && stack.peek().value < value) { // 大于
int times = stack.pop().times; // 在栈中已经存在的次数
long internalSum = getInternalSum(times); // 同数组成的对数
// 栈中数 5 222 来了value=3 对数=222组成的对数 + 222 分别同 5 和 3 组成的对数（times * 2）
res += internalSum + times * 2;
}
if (!stack.isEmpty() && stack.peek().value == value) { // 等于
stack.peek().times++;
} else { // 小于 ，入栈
stack.push(new Pair(value));
}
index = nextIndex(size, index);
}
while (!stack.isEmpty()) { // 经过上述过程，数组元素遍历完毕，但是栈中还有元素
int times = stack.pop().times;
res += getInternalSum(times);
if (!stack.isEmpty()) { // 排除是最后栈底元素情况
res += times; // 先加一个方向和下一个数的对数
if (stack.size() > 1) { // 不是最后两位数
res += times;
} else {
res += stack.peek().times > 1 ? times : 0; // 栈底元素只有入一次栈
// 5 222 2只能向一个方向找到5，另一个方向找到的是同一个5，不需要。
}
}
}
return res;
}
}
