我的穷举法这次不仅内存占用超出了，而且还超出了浏览器所能承受的最大限制,报错了
下面的是我把 Java 解法改成 JS 的
(function () {
const n = 8;
let arr = `186 186 150 200 160 130 197 200`.split(" ");
let left = [],
right = [];
left[0] = 1;
right[n - 1] = 1;
for (let i = 0; i < n; i++) {
left[i] = 1;
for (let j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
left[i] = Math.max(left[j] + 1, left[i]);
}
}
}
for (let i = n - 1; i >= 0; i--) {
right[i] = 1;
for (let j = n - 1; j > i; j--) {
if (arr[i] > arr[j]) {
right[i] = Math.max(right[i], right[j] + 1);
}
}
}
let result = [];
for (let i = 0; i < n; i++) {
result[i] = left[i] + right[i] - 1;
}
let max = 1;
for (let i = 0; i < n; i++) {
max = Math.max(result[i], max);
}
console.log(n - max);
})();
left数组为[1, 1, 1, 2, 2, 1, 3, 4],存储递增序列长度
186 前面没有算一个
186 前面没有算一个
150 前面没有算一个
200 前面有 186 算两个
160 前面有 150 算一个
130 前面没有算一个
197 前面有 150 160 算三个
200 前面有 150 160 197 算 4 个
right 数组为 [3, 3, 2, 3, 2, 1, 1, 1]存储递减序列长度
186 后面有 150 130 算三个
186 后面有 150 130 算三个
150 后面有 130 算两个
200 后面有 160 130 算三个
160 后面有 130 算两个
130 后面没有算一个
197 后面没有算一个
200 后面没有算一个
把left和right对应索引相加在减一，因为都算了自身
result 为 [3, 3, 2, 4, 3, 1, 3, 4]
那么result数组就是对应索引下符合从左到右递增且从右到左递减的这种规律的序列长度了，总人数减去即可
注意 Math.max(left[j] + 1, left[i]); 因为是双重循环，left[i]在发生left[j] + 1 < left[i]时，left[i]的值必然不是 1 了，当这种情况发生，说前面已经有更长的了，有left[j]的序列要比目前最长的短
基于上述，可以给出知道哪些索引被移除的代码
(function () {
const n = 8;
let arr = `147 186 186 150 200 160 130 197 200`.split(" ");
let left = [],
right = [],
leftInfos = {},
rightInfos = {};
left[0] = 1;
right[n - 1] = 1;
for (let i = 0; i < n; i++) {
left[i] = 1;
leftInfos[i] = [];
for (let j = 0; j < i; j++) {
leftInfos[i][j] = [];
if (arr[i] > arr[j]) {
leftInfos[i][j].push(...(leftInfos[j][j - 1] || []), j);
left[i] = Math.max(left[j] + 1, left[i]);
} else {
leftInfos[i][j] = [...(leftInfos[i][j - 1] || [])];
}
}
}
console.log(leftInfos);
for (let i = n - 1; i >= 0; i--) {
right[i] = 1;
rightInfos[i] = [];
for (let j = n - 1; j > i; j--) {
rightInfos[i][j] = [];
if (arr[i] > arr[j]) {
rightInfos[i][j].push(j, ...(rightInfos[j][j + 1] || []));
right[i] = Math.max(right[i], right[j] + 1);
} else {
rightInfos[i][j] = [...(right[i][j + 1] || [])];
}
}
}
console.log(rightInfos);
let result = [];
for (let i = 0; i < n; i++) {
result[i] = left[i] + right[i] - 1;
}
let max = 1;
for (let i = 0; i < n; i++) {
max = Math.max(result[i], max);
}
console.log(n - max);
})();
因为最大长度为 5 是在索引为 4 的地方，此时leftInfos[4]的值为[[0],[0,1],[0,2],[0,3]],分别代表 147 小于 200，147 小于 200 且 186 小于 200,147 小于 200 且 186 小于 200，147 小于 200 且 150 小于 200。
此时rightInfos[4]的值为[[5,6],[6],[7]],再次组合就知道索引，可能的情况有
0,1,4,5,6
0,2,4,5,6
0,3,4,5,6
下面是我穷举的解法，其实对于前端来将，这已经能够解决大部分场景了。
124
16 103 132 23 211 75 155 82 32 48 79 183 13 91 51 172 109 102 189 121 12 120 116 133 79 120 116 208 47 110 65 187 69 143 140 173 203 35 184 49 245 50 179 63 204 34 218 11 205 100 90 19 145 203 203 215 72 108 58 198 95 116 125 235 156 133 220 236 125 29 235 170 130 165 155 54 127 128 204 62 59 226 233 245 46 3 14 108 37 94 52 97 159 190 143 67 24 204 39 222 245 233 11 80 166 39 224 12 38 13 85 21 47 25 180 219 140 201 11 42 110 209 77 136
如上数据说是内存超了，我把代码到本地执行，已经报错了。
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let lineList = [];
rl.on("line", function (line) {
lineList.push(line);
});
function combination(S, k) {
if (k === 0 || S.length === k) {
return [S.slice(0, k)];
}
const [first, ...others] = S;
let r = [];
r = r.concat(combination(others, k - 1).map((c) => [first, ...c]));
r = r.concat(combination(others, k));
return r;
}
rl.on("close", function (line) {
const heightList = lineList[1].split(" ");
let num = 0,
resultList = [[]],
indexList = Array(heightList.length)
.fill(1)
.map((item, i) => i);;
for (let i = 0; i < resultList.length; i++) {
let dataList = [...heightList];
resultList[i].forEach((el, index) => {
dataList.splice(el - index, 1);
});
let middleIndex = 0;
for (let j = 0; j < dataList.length - 1; j++) {
if (dataList[j + 1] > dataList[j]) {
middleIndex = j + 1;
} else {
break;
}
}
let lastIndex = 0;
if (middleIndex != 0 && middleIndex != dataList.length - 1) {
for (let h = middleIndex; h < dataList.length - 1; h++) {
if (dataList[h + 1] < dataList[h]) {
lastIndex = h;
} else {
break;
}
}
}
if (lastIndex == dataList.length - 2) {
break;
}
if (i === resultList.length - 1) {
i = -1;
num++
resultList = combination(indexList,num);
}
}
console.log(num);
});
combination(['A'，'B','C'],2)能够得到所有两两组合，这已经是优化版本，就是先一个都不移除，看符不符合，在移除一个、两个，之前的版本因为要借助一个的形成两个的组合，所以要都保留，但数据够大时，对内存的占用的减少依旧杯水车薪。
一次算出所有组合再按照个数排序
Array(count)
.fill(1)
.map((item, i) => i)
.forEach((item) => {
let list = [[item]];
resultList.forEach((arr) => {
list.push([...arr, item]);
});
resultList.push(...list);
});
resultList.sort((a, b) => a.length - b.length);
借着就是判断移除好的数组符不符合要求了。
