我的窮舉法這次不僅內(nèi)存占用超出了，而且還超出了瀏覽器所能承受的最大限制,報錯了
下面的是我把 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數(shù)組為[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 數(shù)組為 [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對應(yīng)索引相加在減一晴裹，因為都算了自身
result 為 [3, 3, 2, 4, 3, 1, 3, 4]
那么result數(shù)組就是對應(yīng)索引下符合從左到右遞增且從右到左遞減的這種規(guī)律的序列長度了田盈，總?cè)藬?shù)減去即可
注意 Math.max(left[j] + 1, left[i]); 因為是雙重循環(huán)，left[i]在發(fā)生left[j] + 1 < left[i]時尿这，left[i]的值必然不是 1 了簇抵，當這種情況發(fā)生，說前面已經(jīng)有更長的了妻味，有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
下面是我窮舉的解法嘉裤，其實對于前端來將，這已經(jīng)能夠解決大部分場景了栖博。
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
如上數(shù)據(jù)說是內(nèi)存超了屑宠，我把代碼到本地執(zhí)行，已經(jīng)報錯了仇让。
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)能夠得到所有兩兩組合，這已經(jīng)是優(yōu)化版本丧叽，就是先一個都不移除卫玖，看符不符合，在移除一個踊淳、兩個假瞬，之前的版本因為要借助一個的形成兩個的組合，所以要都保留迂尝，但數(shù)據(jù)夠大時脱茉，對內(nèi)存的占用的減少依舊杯水車薪。
一次算出所有組合再按照個數(shù)排序
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);
借著就是判斷移除好的數(shù)組符不符合要求了垄开。
