LeetCode 2444、1906、2682 题解（枚举右，维护左，前缀和）

今日又是被leetcode摧残的一天，一道困难题，但不是困难题的难度，但是说实话有点难想，也随机了一些别的题来磨练自己，不多比比，开始整理今天的思路。

输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。

整理一下情况：

对于该题我的思路是当nums[i]中出现nums[i]>maxK和nums[i]<minK的情况时，对数组进行切割然后分开维护，用数组记录下切割数组后的左右边界，然后通过常规的枚举左和枚举右去实现这个题目。这时候我们就会发现双枚举一定会导致超时，所以我们得在枚举这里下功夫，做到枚举右，维护左。

但这样子的话其实还有许多样例需要去考虑能否实行，例如[2,1,3,5,2,1,5,7,1,5,3]这种切割后是分为[2,1,3,5,2,1,5]和[1,5,3]对于前一种维护，我们又得使得区间不断切换至[1,3,5][5,2,1][1,5]，再通过滑动窗口去找到对应数量的子数组（这又是麻烦的一点）。

之后实在想不到方法后便看了题解，题解对于该题的解决真的非常巧妙，我是想不出来的，题解通过定义几个变量进行维护和遍历del维护限制的数值和数组的关系并获取l的数值，通过down和up加上Math.min方法不断切换区间并获取r的数值，当r>=l，便能使得子数组成立，而子数组数量则成为了边界的加减法

以下便是此题的解法所在，枚举右，维护左

class Solution {public long countSubarrays(int[] nums, int minK, int maxK) {int n = nums.length;long ans = 0;for (int i = 0, up = -1, down = -1, del = -1; i < n; i++) {if (nums[i] == minK) {down = i;}if (nums[i] == maxK) {up = i;}if (nums[i] > maxK || nums[i] < minK) {del = i;}int l = del + 1, r = Math.min(down, up);System.out.println("l:"+l+"r:"+r);if (r >= l) {ans += r - l + 1;}}return ans;}}

今天除了该题，还做了一道很难想的前缀和题目，还是一样，先理清自己的思路，再弄清楚题解的思路，其实我也应该再去敲一遍代码的，再敲一遍也不一定能敲出来。

输入：nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
输出：[2,1,4,1]
解释：查询结果如下：
- queries[0] = [0,1]：子数组是 [1,3] ，差绝对值的最小值为 |1-3| = 2 。
- queries[1] = [1,2]：子数组是 [3,4] ，差绝对值的最小值为 |3-4| = 1 。
- queries[2] = [2,3]：子数组是 [4,8] ，差绝对值的最小值为 |4-8| = 4 。
- queries[3] = [0,3]：子数组是 [1,3,4,8] ，差的绝对值的最小值为 |3-4| = 1 。

对于该题我的思路是通过二分的方式实现前缀和再开一个二维数组去维护，例如[1,3,4,8]
一开始的区间是[0,3]，之后的区间便通过二分的方式使得区间遍历至[0,2]和[1,3]，然后再遍历至[0,1]、[1,2]和[2,3]

维护好每个区间的差绝对值最小值后，再根据queries找到对应的二维数组的区间，得到对应的值存放至数组中。

但这也只是错误的思路，真正正确的思路应该是用前缀和维护数值和数量，而构建的二维数组大小应该为101，因为根据题目的nums数值区间可以得到1<=nums[i]<=100

i	1	2	3	4	5	…	100
0 (空数组)	0	0	0	0	0	…	0
1 (看到1)	1	0	0	0	0	…	0
2 (看到3)	1	0	1	0	0	…	0
3 (看到4)	1	0	1	1	0	…	0
4 (看到8)	1	0	1	1	0	…	1

通过二维数组去确定数值
prefix[l][j]和prefix[r][j]，l确定左边界，r确定右边界，而j则遍历1-100的数值，用右边界的二维数组得到的值减去左边界的二维数组得到的值如果大于0则说明该数值存在于当前的[l,r]区间中，那这时候我们就有疑问了，差的绝对值最小值我们还没计算啊，这就是通过该二维数组维护的妙处，通过j对数值在区间1-100之间的顺序遍历，相当于帮你sort一遍数组后，直接用后面减前面的数值再通过Math.min方法找到最小值。

class Solution {public int[] minDifference(int[] nums, int[][] queries) {int n = nums.length;int[][] pre = new int[n+1][101];for(int i=0;i<n;i++){for(int j=0;j<101;j++)pre[i+1][j] = pre[i][j]; // 将前面的前缀信息也记录起来pre[i+1][nums[i]]++;}int size = queries.length;int[] ans = new int[size];for(int i=0;i<size;i++){int left=queries[i][0], right=queries[i][1];int minValue=Integer.MAX_VALUE, last=-1;for(int j=1;j<=100;j++){if(pre[left][j] < pre[right+1][j]){ // 证明存在if(last != -1)minValue = Math.min(minValue, j-last);last = j;}}if(minValue == Integer.MAX_VALUE)minValue = -1;ans[i] = minValue;}return ans;}
}

除了这两道很有难度且有想法的题目，还做了一道面向答案的简单题。

这个题目虽然我找到了对应的规律，但还是有一个误区，测试过比较多的样例才找到了该误区。

根据图中所示，我们可以明白通过题目给的n和k，我们可以得到规律，先初始化start=1，然后通过start=(start+i*k)%n，但有一个情况会出现，就是当(start+i*k)%n==0时，其实start的值应该为n，但却会由于该公式变为0，所以我们需要通过调判来改变一下start即可。

判断重复的话用map或者set都能维护，看个人喜好。最重要的果然还是list转数组的这个方法losers.stream().mapToInt(Integer::intValue).toArray()

class Solution {public int[] circularGameLosers(int n, int k) {int ans = 0;int mid = 1;HashMap<Integer,Integer> map = new HashMap<>();map.put(1,1);int start = 0;if(k+1<=n) start=k+1;else start=(k+1)%n;while(ans!=2){mid++;map.put(start,map.getOrDefault(start,0)+1);ans = map.get(start);if((start+mid*k)%n==0) start = n;else start = (start+mid*k)%n;}// 找出没有访问过的玩家编号List<Integer> losers = new ArrayList<>();for (int i = 1; i <= n; i++) {if (map.getOrDefault(i,0)==0) {losers.add(i);}}// 将List转换为数组return losers.stream().mapToInt(Integer::intValue).toArray();}
}