100180. Find Polygon With the Largest Perimeter
给你一个长度为 n 的 正 整数数组 nums 。
多边形 指的是一个至少有 3 条边的封闭二维图形。多边形的 最长边 一定 小于 所有其他边长度之和。
如果你有 k （k >= 3）个 正 数 a1，a2，a3, ...，ak 满足 a1 <= a2 <= a3 <= ... <= ak 且 a1 + a2 + a3 + ... + ak-1 > ak ，那么 一定 存在一个 k 条边的多边形，每条边的长度分别为 a1 ，a2 ，a3 ， ...，ak 。
一个多边形的 周长 指的是它所有边之和。
请你返回从 nums 中可以构造的 多边形 的 最大周长 。如果不能构造出任何多边形，请你返回 -1 。
测试样例：
输入：nums = [5,5,5]
输出：15
解释：nums 中唯一可以构造的多边形为三角形，每条边的长度分别为 5 ，5 和 5 ，周长为 5 + 5 + 5 = 15 。
解答：排序之后，记录到当前数字之前的和。如果sum(a1, a2, .., ak-1) < ak，又因为排序了，所以必然有ak > ak-1，则当前必然是一个多边形。
class Solution {
public long largestPerimeter(int[] nums) {
Arrays.sort(nums);
long res = -1, sum = 0;
for (int i = 0; i < nums.length; ++i) {
if (sum > nums[i]) {
res = Math.max(res, sum + nums[i]);
}
sum += nums[i];
}
return res;
}
}100167. Count the Number of Incremovable Subarrays II
给你一个下标从 0 开始的 正 整数数组 nums 。
如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。
请你返回 nums 中 移除递增 子数组的总数目。
注意 ，剩余元素为空的数组也视为是递增的。
子数组 指的是一个数组中一段连续的元素序列。
测试样例：
输入：nums = [1,2,3,4]
输出：10
解释：10 个移除递增子数组分别为：[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4] 和 [1,2,3,4]。移除任意一个子数组后，剩余元素都是递增的。注意，空数组不是移除递增子数组。
解答：如果当前已经是一个严格递增序列，则用等差数列求和公式计算一下结果。否则我们需要将从0开始的升序序列寻找到，并存在一个红黑树中，然后从后向前遍历数组。从后向前遍历的时候需要保证后序数组也是严格递增序列。那么这个时候，我们可以利用红黑树，寻找到一个前置序列，这个序列拼接上后置序列也是一个严格升序序列。利用这个性质，我们可以求出当前位置，满足条件的移除递增 子数组。
class Solution {
public long incremovableSubarrayCount(int[] nums) {
TreeMap<Integer, Integer> increase = new TreeMap<>();
for (int i = 0; i < nums.length; ++i) {
if (i == 0 || nums[i] > nums[i - 1]) {
increase.put(nums[i], i);
} else {
break;
}
}
int max = increase.lastEntry().getValue();
if (max == nums.length - 1) {
return (1L + nums.length) * nums.length / 2;
}
long res = increase.lastEntry().getValue() + 2;
for (int i = nums.length - 1; i >= 0; --i) {
if (i == nums.length - 1 || nums[i] < nums[i + 1]) {
Map.Entry<Integer, Integer> lower = increase.lowerEntry(nums[i]);
if (lower == null) {
res += 1;
} else {
res += lower.getValue() + (i <= max ? 1 : 2);
}
} else {
break;
}
}
return res;
}
}100141. Find Number of Coins to Place in Tree Nodes
给你一棵 n 个节点的 无向 树，节点编号为 0 到 n - 1 ，树的根节点在节点 0 处。同时给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
给你一个长度为 n 下标从 0 开始的整数数组 cost ，其中 cost[i] 是第 i 个节点的 开销 。
你需要在树中每个节点都放置金币，在节点 i 处的金币数目计算方法如下：
- 如果节点 i 对应的子树中的节点数目小于 3 ，那么放 1 个金币。
- 否则，计算节点 i 对应的子树内 3 个不同节点的开销乘积的 最大值 ，并在节点 i 处放置对应数目的金币。如果最大乘积是 负数 ，那么放置 0 个金币。
请你返回一个长度为 n 的数组 coin ，coin[i]是节点 i 处的金币数目。
测试样例：
输入：edges = [[0,1],[0,2],[0,3],[0,4],[0,5]], cost = [1,2,3,4,5,6]
输出：[120,1,1,1,1,1]
解释：在节点 0 处放置 6 5 4 = 120 个金币。所有其他节点都是叶子节点，子树中只有 1 个节点，所以其他每个节点都放 1 个金币。
解答：这题没啥难度，注意2个负数相乘也是正数（因为这个WA了一次，泪目）。每个节点都记录一下当前最大的3个正数和负数，然后计算一下当前节点的最大乘积。
class Solution {
private class PersonnelQueue {
LinkedList<Integer> pos;
LinkedList<Integer> neg;
public PersonnelQueue() {
pos = new LinkedList<>();
neg = new LinkedList<>();
}
public boolean isValid() {
return pos.size() + neg.size() >= 3;
}
public void add(int n) {
if (n >= 0) {
pos.add(n);
Collections.sort(pos);
if (pos.size() > 3) {
pos.removeFirst();
}
} else {
neg.add(n);
Collections.sort(neg);
if (neg.size() > 3) {
neg.removeLast();
}
}
}
public long findBest() {
long res = 0;
if (neg.size() >= 2 && pos.size() >= 1) {
long tmp = neg.get(0);
tmp *= neg.get(1);
tmp *= pos.get(pos.size() - 1);
res = Math.max(res, tmp);
}
if (pos.size() >= 3) {
long tmp = 1;
for (int n : pos) {
tmp *= n;
}
res = Math.max(res, tmp);
}
return res;
}
}
public long[] placedCoins(int[][] _edges, int[] cost) {
int len = _edges.length + 1;
List<Integer>[] edges = new List[len + 1];
for (int i = 0; i < len; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
long[] res = new long[len];
dfs(0, -1, edges, cost, res);
return res;
}
private PersonnelQueue dfs(int node, int pre, List<Integer>[] edges, int[] cost, long[] res) {
PersonnelQueue queue = new PersonnelQueue();
for (int n : edges[node]) {
if (n != pre) {
PersonnelQueue tmp = dfs(n, node, edges, cost, res);
for (int t : tmp.neg) {
queue.add(t);
}
for (int t : tmp.pos) {
queue.add(t);
}
}
}
queue.add(cost[node]);
if (queue.isValid()) {
res[node] = queue.findBest();
} else {
res[node] = 1;
}
return queue;
}
}