1. 3658 奇數和與偶數和的最大公約數（歐幾里得）

鏈接：題目鏈接
題解：

題解時間復雜度O(logmin(a, b))：

1. 獲得前n個奇、偶數的總和，由于數列為等差數列，等差數列和公式：(a1 + an) * n / 2），可以快速求和。
2. 獲取兩個數字的最大公約數，用歐幾里得算法可求得最大公約數，代碼模版如下。

代碼：

    class Solution {public int gcd(int a, int b) {return b != 0 ? gcd(b, a % b) : a;}public int gcdOfOddEvenSums(int n) {// 等差數列求和int sum1 = (1 + 2 * n - 1) * n / 2;int sum2 = (2 + 2 * n) * n / 2;return gcd(sum1, sum2);}
}

2. 3659 數組元素分組（抽屜原理）

鏈接：題目鏈接
題解：

題解時間復雜度O(n):

1. nums 中的每個元素必須被分配到恰好一個組中，每個組恰好k個不同的元素，說明 n * k = 數組長度，n為具體組數。
2. 組數 = 數組長度 / k，如果某個數字重復次數 > 組數，那么肯定沒辦法滿足每個組恰好k個不同的元素（抽屜原理），反之均可滿足。

代碼：

class Solution {public boolean partitionArray(int[] nums, int k) {int len = nums.length;if (len % k != 0) {return false;}int countLimit = len / k;Map<Integer, Integer> numCountMap = new HashMap<>();for (int num: nums) {numCountMap.put(num, numCountMap.getOrDefault(num, 0) + 1);}return numCountMap.values().stream().noneMatch(numCount -> numCount > countLimit);}
}

3. 3660 跳躍游戲 9（預處理 單調棧 二分解法）

鏈接：題目鏈接
題解：

背景：僅當 nums[j] < nums[i] 時，才允許跳躍到下標 j，其中 j > i。 僅當 nums[j] > nums[i] 時，才允許跳躍到下標 j，其中 j < i。（一次跳躍中，往前跳，nums值必須嚴格大于; 往后跳，nums值必須嚴格小于）;
題解時間復雜度O(nlogn)：

1. 對于第i個元素，如果能到達的最大值在左側，那么一次跳躍即可（需要維護左側最大值）。
2. 對于第i個元素，如果能到達的最大值在右側，首先往右跳躍到j位置，nums[j] < nums[i]的，所以nums[j]肯定不是i元素能到達的最大值，意味著還得從j下標往左跳，才有可能 num[j] > nums[i]。
3. 注意：對于第i個元素，最大值在右側還有一種跳躍方式。可能存在[30, 10, 35, 22] 這種情況，對于nums[1]來說，并不能直接跳到35去（因為nums[2、3] > nums[1]），但是有一條路線可以達到nums[3](1 -> 0 -> 3 -> 2)，(第2、3點)總結：對于最大值在右側情況，nums[i]可以先跳到左側最大值（nums[j] >= nums[i]），再往右側跳（覆蓋的范圍更廣）
4. 因為要在logn級別找到 i右邊元素到達的最大值，那么很自然想到了維護一個有序的列表，通過二分方式在logn時間復雜度找到右側能到達的最大值。這里維護有序列表有個關鍵點：如果 2能到達x，3能達到x-1或者x，那么這個列表還有必要維護3這個元素嗎？答案是不需要將3這個元素入隊(因為能到達2的元素包含了能到達3的元素 且 3能到達的最大值<=2能到達的最大值)，也就是單調棧思想
5. 有序列表樣例：[1 -> 10, 2 -> 12, 5 -> 15]，此時有序是指的nums[i]是遞增的，且nums[i]能找到的最大值也是遞增的。所以在二分查找的時候只需要找到小于nums[i]的第一個元素，再拿到它對應的最大值即可。
6. 第i個元素能到達的最大值 = max(左側最大值, 右側最大值)

代碼：

 class Solution {public int[] maxValue(int[] nums) {int len = nums.length;int[] leftMaxValues = new int[len];int maxValue = 0;for (int i = 0; i < len; ++ i) {maxValue = Math.max(maxValue, nums[i]);leftMaxValues[i] = maxValue;}int[] result = new int[len];TreeMap<Integer, Integer> map = new TreeMap<>();// 初始化result[len - 1] = leftMaxValues[len - 1];map.put(nums[len - 1], leftMaxValues[len - 1]);for (int i = len - 2; i >= 0; -- i) {// 獲取右邊最大值Map.Entry<Integer, Integer> entry = map.lowerEntry(leftMaxValues[i]);if (entry != null) {result[i] = entry.getValue();} else {result[i] = leftMaxValues[i];}// 維護mapInteger old = map.get(nums[i]);if (old == null || old < result[i]) {map.put(nums[i], result[i]);// 刪除所有 "比nums[i]大，且 value <= result[0]" 的節點while (true) {Map.Entry<Integer, Integer> higher = map.higherEntry(nums[i]);if (higher != null && higher.getValue() <= result[i]) {map.remove(higher.getKey());} else break;}}}return result;}}

4. 3661 可以被機器人摧毀的最大墻壁數目（DP解法）

鏈接：題目鏈接
題解：

題解 時間復雜度O(nlogn)：

1. 因為機器人會阻擋子彈的穿透，所以第i個機器人，最多穿透[i - 1, i + 1]下標的區域，那么也以為著第i個機器人只與第i-1、i+1個機器人有關系
2. robot、distance 為一組信息 walls為一組信息，兩組信息分別排序（機器人跟相鄰機器人有關系 所以需要排序處理）
3. 這里機器人只能往左往右發射，可以用f[i][j] i表示第i個機器人 j表示往左還是右設計 j為0 往左 j為1往右
4. dp轉移方程式： f[i][1] = Math.max(f[i - 1][0], f[i - 1][1]) + i機器人往右打多少個墻； f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]) + i機器人往左打多少個墻
5. 打多少個墻？可以拿到機器人射擊區間，因為墻列表也做了排序（是有序的），再通過二分計算能射擊多少個墻
6. 注意1：這里要注意i-1機器人往右，i機器人往左射擊的情況，對射的情況（避免重復計算墻）
7. 注意2：這里要考慮機器人與墻重合的情況，比如i機器人與墻重合，但是i-1機器人往右射擊 計算了該墻，但是i機器人射擊又計算該墻的情況（又重復計算了），所以墻與機器人重合情況，該墻只讓該機器人射擊。（i-1機器人往右射擊，區間從[nums[i-1], nums[i]] -> [nums[i-1], nums[i] -1)）

代碼：

class Solution {class Pair implements Comparable<Pair>{private int robotIndex;private int distance;@Overridepublic int compareTo(Pair pair) {return robotIndex - pair.robotIndex;}public Pair(int robotIndex, int distance) {this.robotIndex = robotIndex;this.distance = distance;}}public int maxWalls(int[] robots, int[] distance, int[] walls) {int len = robots.length;List<Pair> pairs = new ArrayList<>(len);for (int i = 0; i < len; ++ i) {pairs.add(new Pair(robots[i], distance[i]));}Collections.sort(pairs);Arrays.sort(walls);int[][] f = new int[len + 1][2];for (int i = 1; i <= len; ++ i) {if (i == 1) {f[i][1] = caclSum(0, pairs, pairs.get(0).distance, walls, false, true);f[i][0] = caclSum(0, pairs, pairs.get(0).distance, walls, true, true);} else {f[i][1] = Math.max(f[i - 1][0], f[i - 1][1]) + caclSum(i - 1, pairs, pairs.get(i - 1).distance, walls, false, true);Pair pair = pairs.get(i - 1);Pair prePair = pairs.get(i - 2);if (pair.distance + prePair.distance >= pair.robotIndex - prePair.robotIndex) {f[i][0] = Math.max(f[i - 1][0] + caclSum(i - 1, pairs, pair.distance, walls, true, true), Math.max(f[i][0], Math.max(f[i - 2][0], f[i - 2][1]) + caclSum(i - 2, pairs, pair.distance + prePair.distance, walls, false, false)));} else {f[i][0] = Math.max(f[i - 1][1], f[i - 1][0]) + caclSum(i - 1, pairs, pair.distance, walls, true, true);}}}return Math.max(f[len][0], f[len][1]);}public int caclSum(int index, List<Pair> pairs, int distance, int[] walls, boolean left, boolean excludeNextIndex) {int l, r;if (left) {r = pairs.get(index).robotIndex;l = r - distance;if (index - 1 >= 0) {l = Math.max(l, pairs.get(index - 1).robotIndex + (excludeNextIndex ? 1 : 0));}} else {l = pairs.get(index).robotIndex;r = l + distance;if (index + 1 < pairs.size()) {r = Math.min(r, pairs.get(index + 1).robotIndex - (excludeNextIndex ? 1 : 0));}}int wallLIndex, wallRIndex;// 找到大于等于l的第一個下標int wallL = 0, wallR = walls.length - 1;while (wallL < wallR) {int mid = (wallL + wallR) >> 1;if (walls[mid] >= l) {wallR = mid;} else {wallL = mid + 1;}}wallLIndex = wallL;// 找到小于等于R的第一個下標wallL = 0;wallR = walls.length - 1;while (wallL < wallR) {int mid = (wallL + wallR + 1) >> 1;if (walls[mid] <= r) {wallL = mid;} else {wallR = mid - 1;}}wallRIndex = wallL;if (wallLIndex <= wallRIndex && walls[wallLIndex] >= l && walls[wallRIndex] <= r) {return wallRIndex - wallLIndex + 1;}return 0;}
}

如果對你有幫助，辛苦點個贊，謝謝啦，朋友！！！