左神高级进阶班3（TreeMap顺序表记录线性数据的使用， 滑动窗口的使用，前缀和记录结构， 可能性的舍弃）

目录

【案例1】

【题目描述】

【思路解析】

【代码实现】

【案例2】

【题目描述】

【思路解析】

【代码实现】

【案例3】

【题目描述】

【思路解析】

【代码实现】

【案例4】

【题目描述】

 【思路解析】

【代码实现】

---

【案例1】

【题目描述】

【思路解析】

这里大楼之间有重叠部分，然后让我们描述轮廓线数组，所以我们需要知道每个点的最大高度。因为他每一个楼中间部分是高度相等的，所以我们只需要知道这个点所在地点那个楼是最高的，并且因为楼中间部分高度相等，所以我们只关心每栋楼的开始位置和结束位置。我们可以通过matrix构建一个这样的数组【数组存放结点，结点包括位置，升降情况，高度三个信息】，数组通过位置和升降情况来进行排序，（1）先按照位置来排序，升序（2）如果两个位置相同，则开始位置（升的情况）排在前。

通过这样的顺序数组，我们就可以构建一个高度和出现的顺序表，升就添加一个记录，降就删除一个记录，如果记录为0，则删除。通过这个顺序表，就可以知道当前位置的最大高度（位置和最大高度的关系也构建一个顺序表存放，使在生成轮廓时，轮廓位置变化是有序的），通过高度的变化我们就可以知道轮廓的变化，然后通过位置和最大高度的顺序表构建轮廓数组。

【代码实现】

package AdvancedPromotion3;import java.util.*;/*** @ProjectName: study3* @FileName: Ex1* @author:HWJ* @Data: 2023/9/18 10:27*/
public class Ex1 {public static void main(String[] args) {int[][] matrix = {{2, 5, 6}, {1, 7, 4}, {4, 6, 7}, {3, 6, 5}, {10, 13, 2}, {9, 11, 3}, {12, 14, 4}, {10, 12, 5}};List<List<Integer>> ans = getContourMatrix(matrix);for (List<Integer> integers : ans) {for (int i : integers) {System.out.print(i + " ");}System.out.println();}}public static class Node {int x;boolean isAdd; // true 表示当前为一个楼的开始， false表示当前地点为一个楼的结束int height;public Node(int x, boolean isAdd, int height) {this.x = x;this.isAdd = isAdd;this.height = height;}}public static class NodeComparator implements Comparator<Node> {@Overridepublic int compare(Node o1, Node o2) {if (o1.x != o2.x) {return o1.x - o2.x;}if (o1.isAdd != o2.isAdd) {return o1.isAdd ? -1 : 1;}return 0;}}public static List<List<Integer>> getContourMatrix(int[][] matrix) {Node[] nodes = new Node[matrix.length * 2];for (int i = 0; i < matrix.length; i++) {nodes[i * 2] = new Node(matrix[i][0], true, matrix[i][2]);nodes[i * 2 + 1] = new Node(matrix[i][1], false, matrix[i][2]);}Arrays.sort(nodes, new NodeComparator());TreeMap<Integer, Integer> heightAndNums = new TreeMap<>();TreeMap<Integer, Integer> maxHeight = new TreeMap<>();for (Node node : nodes) {if (node.isAdd) {if (!heightAndNums.containsKey(node.height)) { //如果不存在就新建记录heightAndNums.put(node.height, 1);} else {heightAndNums.put(node.height, heightAndNums.get(node.height) + 1);}} else {if (heightAndNums.get(node.height) == 1) { // 如果只剩一条记录了就直接删除heightAndNums.remove(node.height);} else {heightAndNums.put(node.height, heightAndNums.get(node.height) - 1);}}if (heightAndNums.isEmpty()) { // 这里通过顺序表记录当前结点的最大高度maxHeight.put(node.x, 0);} else {maxHeight.put(node.x, heightAndNums.lastKey());}}int preHeight = 0;int start = 0;List<List<Integer>> res = new ArrayList<>();for (int x : maxHeight.keySet()) {int curHeight = maxHeight.get(x);if (preHeight != curHeight) { // 如果高度发生了变化，就构建轮廓if (preHeight != 0) { // 如果之前的高度为0， 说明之前的那个地方到现在的地方没有楼res.add(new ArrayList<>(Arrays.asList(start, x, preHeight)));}preHeight = curHeight;start = x;}}return res;}
}

【案例2】

【题目描述】

【思路解析】

用滑动窗口解决，如果当前窗口的元素和大于k，l++，小于k，r++，如果==k，记录答案，并且r++。

因为是正数数组，所以滑动窗口在移动过程能维持单调性。保证答案的正确性。

【代码实现】

package AdvancedPromotion3;/*** @ProjectName: study3* @FileName: Ex2* @author:HWJ* @Data: 2023/9/18 11:07*/
public class Ex2 {public static void main(String[] args) {int[] arr = {1,2,3,1,1,1,2,1,1,3};System.out.println(getMaxLen(arr, 3));}public static int getMaxLen(int[] arr, int k){int l = 0;int r = 0;int sum = 0;int res = -1;while (r < arr.length){if (sum == k){res = Math.max(r - l + 1, res);r++;if (r == arr.length){break;}sum += arr[r];}if (sum > k){sum -= arr[l++];}if (sum < k){r++;if (r == arr.length){break;}sum += arr[r];}}return res;}
}

【案例3】

【题目描述】

给定一个无序数组arr，其中元素可正、可负、可0，给定一个整数k。求arr所有的子数组中累加和等于k的最长子数组长度。

【思路解析】

构建一个哈希表，里面放入前缀和和达到这个前缀和的索引位置。加入k = 5。

哈希表有一个记录为 12，i。表示 0--i、这所有的元素和为12，如果在遍历中有一次前缀和为17，所有为j（j > i），则i+1 --- j的累加和应该为k。记录答案即可。

【代码实现】

package AdvancedPromotion3;import java.util.HashMap;/*** @ProjectName: study3* @FileName: Ex3* @author:HWJ* @Data: 2023/9/18 11:17*/
public class Ex3 {public static void main(String[] args) {}public static int getMaxLen(int[] arr, int k){if (arr.length == 0){return 0;}HashMap<Integer, Integer> sumIndex = new HashMap<>();sumIndex.put(0, -1);int res = -1;int sum = 0;for (int i = 0; i < arr.length; i++) {sum += arr[i];if (sumIndex.containsKey(sum - k)){res = Math.max(res, i - sumIndex.get(sum - k));}sumIndex.put(sum, i);}return res;}
}

  

【案例4】

【题目描述】

 【思路解析】

构建两个数组表示，一个数组minSum【i】表示从i开始最远能达到的地方，并且使这个子数组的和最小；minIndex【i】表示从i开始最远能达到的地方的索引。

例如：表格第一行表示无序数组arr，第二行表示minSum，第三行表示minIndex

3	-2	-4	0	6
-3	-6	-4	0	6
3	3	3	3	4

得到这个之后就相当于把一个数组分成了几个部分，然后我们通过minIndex可以找到下一个部分的开头，我们只考虑下一次能不能加入下一个部分。

例如

我们在第0位置开始遍历，加入了三个部分，达到了k位置，但是他不能加入下一个部分了，我们便从1开始遍历，看他能不能加入下一个部分。我们默认1-k合法，因为如果他不合法，他一定不能加入下一个部分，所以他的有效大小一定小于0-k，我们需要求最大有效长度，所以它一定不是有效解，所以我们直接默认他为合法，只有他能加入下一个区域，我们才把他作为答案的可能，这样可以舍弃很多无效可能性，降低算法复杂度。

【代码实现】

package AdvancedPromotion3;/*** @ProjectName: study3* @FileName: Ex4* @author:HWJ* @Data: 2023/9/18 12:10*/
public class Ex4 {public static void main(String[] args) {int[] arr = {3,-2,-4,0,6};System.out.println(getMaxLen(arr, -2));}public static int getMaxLen(int[] arr, int k){int n = arr.length;int[] minSub = new int[n];int[] minIndex = new int[n];minSub[n - 1] = arr[n - 1];minIndex[n - 1] = arr[n - 1];for (int i = n - 2; i >= 0; i--) {if (minSub[i + 1] <= 0){minSub[i] = arr[i] + minSub[i + 1];minIndex[i] = minIndex[i + 1];}else {minSub[i] = arr[i];minIndex[i] = i;}}int res = 0;int p = 0;int sum = 0;boolean loop =true; // 使第一次进入求解答案时，能正确进入循环for (int i = 0; i < n; i++) {while (p < n && (loop || sum <= k)){ // 这里不初始化p 和 sum，这样可以舍弃大量不是最优解的解。res = Math.max(res, p - i);sum += minSub[p];p = minIndex[p] + 1;loop = false;}sum -= arr[i];}return res;}
}