题单来源

https://leetcode.cn/problems/beautiful-towers-ii/solutions/2456562/qian-hou-zhui-fen-jie-dan-diao-zhan-pyth-1exe/

题目列表

42. 接雨水

https://leetcode.cn/problems/trapping-rain-water/description/

每个位置的雨水最大可能高度是由左右两边的最小高度决定的。

class Solution {public int trap(int[] height) {int n = height.length, ans = 0;int[] l = new int[n], r = new int[n];for (int i = 1; i < n; ++i) {l[i] = Math.max(l[i - 1], height[i - 1]);}for (int j = n - 2; j >= 0; --j) {r[j] = Math.max(r[j + 1], height[j + 1]);ans += Math.max(0, Math.min(l[j], r[j]) - height[j]);}return ans;}
}

238. 除自身以外数组的乘积

https://leetcode.cn/problems/product-of-array-except-self/description/

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] ans = new int[n];ans[0] = 1;for (int i = 0; i < n - 1; ++i) ans[i + 1] = ans[i] * nums[i];int x = 1;for (int i = n - 1; i >= 0; --i) {ans[i] *= x;x *= nums[i];}return ans;}
}

2256. 最小平均差

https://leetcode.cn/problems/minimum-average-difference/description/

提示：

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5

这题需要注意的点：
不能除以 0。
求和需要使用 long。

class Solution {public int minimumAverageDifference(int[] nums) {int n = nums.length;long[] sum = new long[n];for (int i = n - 2; i >= 0; --i) sum[i] = sum[i + 1] + nums[i + 1];long s = 0, mn = Integer.MAX_VALUE;int ans = 0;for (int i = 0; i < n - 1; ++i) {s += nums[i];long x = Math.abs(s / (i + 1) - sum[i] / (n - i - 1));if (x < mn) {mn = x;ans = i;}}if ((s + nums[n - 1]) / n < mn) ans = n - 1;return ans;}
}

2483. 商店的最少代价

https://leetcode.cn/problems/minimum-penalty-for-a-shop/description/

提示：
1 <= customers.length <= 10^5
customers 只包含字符 'Y' 和 'N' 。

代码1——前后缀数组

prev[i] 表示第 i 天关门，在开门期间的代价；suff[i] 表示第 i 天关门，在关门期间的代价。

class Solution {public int bestClosingTime(String customers) {int n = customers.length();int[] prev = new int[n + 1], suff = new int[n + 1];for (int i = 0; i < n; ++i) {prev[i + 1] = prev[i];if (customers.charAt(i) == 'N')  prev[i + 1]++;}for (int i = n - 1; i >= 0; --i) {suff[i] = suff[i + 1];if (customers.charAt(i) == 'Y')  suff[i]++;}int mnV = prev[0] + suff[0], ans = 0;for (int i = 1; i <= n; ++i) {if (prev[i] + suff[i] < mnV) {ans = i;mnV = prev[i] + suff[i];}}return ans;}
}

代码2——$O(1)$空间🐂

https://leetcode.cn/problems/minimum-penalty-for-a-shop/solutions/1993077/qian-hou-zhui-fen-jie-o1-kong-jian-by-en-c2m5/

可以从前往后枚举，只判断当天的状态，（原因是前面的都开门是一样的，后面的都不开门也是一样的）。

class Solution {public int bestClosingTime(String customers) {int ans = 0, balance = 0;// 枚举i，i是最后一个开门的日期for (int i = 0; i < customers.length(); ++i) {if (customers.charAt(i) == 'N') ++balance;else {--balance;if (balance < 0) {ans = i + 1;balance = 0;}}}return ans;}
}

因为对 balance < 0 时有置 0 的操作，所以一旦 balance 再次小于 0 了，就一定是更小的代价。

2420. 找到所有好下标

https://leetcode.cn/problems/find-all-good-indices/description/

提示：
n == nums.length
3 <= n <= 10^5
1 <= nums[i] <= 10^6
1 <= k <= n / 2

递推。

class Solution {public List<Integer> goodIndices(int[] nums, int k) {int n = nums.length;int[] p = new int[n];p[1] = 1;for (int i = 1; i < n - 1; ++i) {if (nums[i] <= nums[i - 1]) p[i + 1] = p[i] + 1;else p[i + 1] = 1;}int suf = 1;List<Integer> ans = new ArrayList<>();for (int i = n - 2; i >= 0; --i) {if (suf >= k && p[i] >= k) ans.add(i);if (nums[i] <= nums[i + 1]) suf++;else suf = 1;}Collections.reverse(ans);return ans;}
}

2167. 移除所有载有违禁货物车厢所需的最少时间

https://leetcode.cn/problems/minimum-time-to-remove-all-cars-containing-illegal-goods/description/

提示：
1 <= s.length <= 2 * 10^5
s[i] 为 '0' 或 '1'

代码1——前后缀分解

分开计算前后缀最小单位时间数，计算前后缀的过程有点动态规划的思想。

class Solution {public int minimumTime(String s) {int n = s.length(), t = 0, ans = n;for (char ch: s.toCharArray()) t += ch == '1'? 1: 0;if (t == 0) return 0;int[] p = new int[n];                       // 前缀p[0] = s.charAt(0) == '1'? 1: 0;for (int i = 1; i < n; ++i) {if (s.charAt(i) == '1') p[i] = Math.min(i + 1, 2 + p[i - 1]);else p[i] = p[i - 1];}int suff = s.charAt(n - 1) == '1'? 1: 0;    // 后缀for (int i = n - 2; i >= 0; --i) {ans = Math.min(ans, suff + p[i]);if (s.charAt(i) == '1') suff = Math.min(n - i, 2 + suff);}return ans;}
}

代码2——简洁写法

pre 表示前面全删和中间删的最小花费，后面的就都是全删，因此可以一次遍历得到结果。

class Solution {public int minimumTime(String s) {int n = s.length();int ans = n, pre = 0;for (int i = 0; i < n; ++i) {if (s.charAt(i) == '1') pre = Math.min(pre + 2, i + 1);ans = Math.min(ans, pre + n - 1 - i);}return ans;}
}

2484. 统计回文子序列数目⭐

https://leetcode.cn/problems/count-palindromic-subsequences/description/

提示：

1 <= s.length <= 10^4
s 只包含数字字符。

前后缀分解，由于要求长度 5，中间的字符可以不管，只要两边的字符对相等即可。
可以从前向后统计各个字符对的个数，再从后向前统计各个字符对的个数，最后在相同位置的相乘，各个位置的结果相加即可。

class Solution {final long MOD = (long)1e9 + 7;public int countPalindromes(String s) {int n = s.length();long[] cnt = new long[10];          // 各个数字出现的次数long[][] pre = new long[n][100];    // 各个位置前缀出现的次数long[] suf = new long[100];         // 后缀出现的次数// 处理前缀for (int i = 0; i < n; ++i) {int v = s.charAt(i) - '0';if (i != 0) {for (int j = 0; j < 100; ++j) pre[i][j] = pre[i - 1][j];}for (int j = 0; j < 10; ++j) {pre[i][j * 10 + v] += cnt[j];}cnt[v]++;}// 处理后缀 和 更新答案Arrays.fill(cnt, 0);long ans = 0;for (int i = n - 1; i >= 2; --i) {int v = s.charAt(i) - '0';for (int j = 0; j < 10; ++j) {int num = j * 10 + v;suf[num] += cnt[j];}// 处理该位置的答案for (int j = 0; j < 100; ++j) {ans = (ans + pre[i - 2][j] * suf[j]) % MOD;}cnt[v]++;}return (int)ans;}
}

相似题目——1930. 长度为 3 的不同回文子序列

https://leetcode.cn/problems/unique-length-3-palindromic-subsequences/description/

提示：
3 <= s.length <= 10^5
s 仅由小写英文字母组成

下面的代码写的很 优雅，用到了一些 位运算表示集合的小技巧，值得学习。

class Solution {public int countPalindromicSubsequence(String s) {int n = s.length();// 用一个int表示字母的集合int[] pre = new int[n + 1], suf = new int[n + 1];for (int i = 0; i < n; ++i) {pre[i + 1] = pre[i] | (1 << (s.charAt(i) - 'a'));}for (int i = n - 1; i >= 0; --i) {suf[i] = suf[i + 1] | (1 << (s.charAt(i) - 'a'));}// 计算以各个字母为中心的回文字符串数量int[] ans = new int[26];for (int i = 1; i < n - 1; ++i) {ans[s.charAt(i) - 'a'] |= (pre[i] & suf[i + 1]);}int res = 0;for (int i = 0; i < 26; ++i) {res += Integer.bitCount(ans[i]);}return res;}
}

2552. 统计上升四元组⭐⭐⭐⭐⭐

https://leetcode.cn/problems/count-increasing-quadruplets/description/

提示：
4 <= nums.length <= 4000
1 <= nums[i] <= nums.length
nums 中所有数字 互不相同 ，nums 是一个排列。

class Solution {public long countQuadruplets(int[] nums) {int n = nums.length;// great[k][x]表示在k右侧大于x的数量int[][] great = new int[n][n + 1];for (int k = n - 2; k >= 2; --k) {great[k] = great[k + 1].clone();// 更新所有比nums[k+1]小的数字xfor (int x = nums[k + 1] - 1; x > 0; --x) { great[k][x]++;}}long ans = 0;int[] less = new int[n + 1];for (int j = 1; j < n - 2; ++j) {// 更新所有比nums[j-1]大的数字xfor (int x = nums[j - 1] + 1; x <= n; ++x) {    less[x]++;}// 计算该位置当作j的答案// 枚举kfor (int k = j + 1; k < n - 1; ++k) {if (nums[j] > nums[k]) {ans += less[nums[k]] * great[k][nums[j]];}}}return ans;}
}

---

进一步优化。

j 右边有 n - 1 - j 个数字，其中 great[j][x] 个数字比 x 大，因此 j 右边有 n - 1 - j - great[j][x] 个数字 <= x，而 x 在 j 右边，所以 j 左边有 x - (n - 1 - j - great[j][x]) 个数字小于 x。
即可省略 less 数组。

class Solution {public long countQuadruplets(int[] nums) {int n = nums.length;// great[k][x]表示在k右侧大于x的数量int[][] great = new int[n][n + 1];for (int k = n - 2; k > 0; --k) {great[k] = great[k + 1].clone();// 更新所有比nums[k+1]小的数字xfor (int x = nums[k + 1] - 1; x > 0; --x) { great[k][x]++;}}long ans = 0;for (int j = 1; j < n - 2; ++j) {// 计算该位置当作j的答案// 枚举kfor (int k = j + 1; k < n - 1; ++k) {int x = nums[k];if (nums[j] > x) {ans += (x - n + 1 + j + great[j][x]) * great[k][nums[j]];}}}return ans;}
}

相同技巧题目——2242. 节点序列的最大得分

https://leetcode.cn/problems/maximum-score-of-a-node-sequence/description/

提示：
n == scores.length
4 <= n <= 5 * 10^4
1 <= scores[i] <= 10^8
0 <= edges.length <= 5 * 10^4
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
不会有重边。

---

枚举作为中间的边。

为了减少循环的复杂度，每个节点只保留最大的那三个邻居节点即可保证答案。

class Solution {int ans = -1;public int maximumScore(int[] scores, int[][] edges) {int n = scores.length;List<Integer>[] g = new List[n];Arrays.setAll(g, e -> new ArrayList<Integer>());for (int[] e: edges) {g[e[0]].add(e[1]);g[e[1]].add(e[0]);}for (int i = 0; i < n; ++i) {Collections.sort(g[i], (x, y) -> scores[y] - scores[x]);if (g[i].size() > 3) g[i] = g[i].subList(0, 3);}for (int[] e: edges) {int x = e[0], y = e[1];for (int a: g[x]) {for (int b: g[y]) {if (a != b && a != y && x != b) {ans = Math.max(ans, scores[x] + scores[y] + scores[a] + scores[b]);}}}}return ans;}
}

Java代码：关于ArrayList.subList(int fromIndex, int toIndex)

注意这里我使用的是 List<Integer>[] g = new List[n];，这是因为后面有 g[i] = g[i].subList(0, 3);，
如果想使用 List<int[]>[] g = new ArrayList[n];，后面就要对应地使用 g[i] = new ArrayList<>(g[i].subList(0, 3));。

参考：为什么不建议用ArrayList的subList方法

建议使用

List<String> subList = new ArrayList<>(list.subList(0,1));

另，subList 的JDK手册：https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ArrayList.html#subList(int,int)

2565. 最少得分子序列⭐⭐⭐⭐⭐（前后缀分解 + 双指针）

https://leetcode.cn/problems/subsequence-with-the-minimum-score/description/

提示：
1 <= s.length, t.length <= 10^5
s 和 t 都只包含小写英文字母。

---

class Solution {public int minimumScore(String s, String t) {int n = s.length(), m = t.length();int[] pre = new int[n + 1], suf = new int[n + 1];// 计算前缀 pre[i]表示s[:i]能匹配的t的最大前缀长度for (int i = 0; i < n; ++i) {pre[i + 1] = pre[i];if (pre[i + 1] < m && s.charAt(i) == t.charAt(pre[i + 1])) pre[i + 1]++;}// 处理后缀 和 答案int ans = m;for (int i = n - 1; i >= 0; --i) {suf[i] = suf[i + 1];ans = Math.min(ans, m - pre[i + 1] - suf[i]);   // pre[i+1]包括s[i],suf[i]暂时还不包括s[i]if (suf[i] < m && s.charAt(i) == t.charAt(m - 1 - suf[i])) suf[i]++;}ans = Math.min(ans, m - pre[0] - suf[0]);   // 特殊处理越界的0return Math.max(ans, 0);}
}