[伯俊]塔#22866を見て
説明:
2つのスタックを使用して問題を解く
順方向スタックと逆方向スタックを使用して、現在の位置を基準にして、高いセットの数を増やします.そして、もしあなたが自分を追加したら、後で探しているビルの高さがもっと低く、あなた自身ももっと高いビルに追加するので、このように計算します.
最後に,ビル間の距離が低いほど優先順位を与え,問題出力要求に合わせる.
Node.説明する
2つのスタックを使用して問題を解く
順方向スタックと逆方向スタックを使用して、現在の位置を基準にして、高いセットの数を増やします.そして、もしあなたが自分を追加したら、後で探しているビルの高さがもっと低く、あなた自身ももっと高いビルに追加するので、このように計算します.
最後に,ビル間の距離が低いほど優先順位を与え,問題出力要求に合わせる.
Node.説明する
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input[0]);
const buildings = input[1].split(' ').map(Number);
const solution = (N, buildings) => {
const countArr = new Array(N).fill(0);
const closestArr = [];
const frontStack = [];
const backStack = [];
for (let i = 0; i < buildings.length; i++) {
const height = buildings[i];
while (frontStack.length && frontStack[frontStack.length - 1][1] <= height)
frontStack.pop();
if (frontStack.length) {
countArr[i] += frontStack.length;
closestArr[i] = {
no: frontStack[frontStack.length - 1][0],
dist: i - frontStack[frontStack.length - 1][0],
};
}
frontStack.push([i, height]);
}
buildings.reverse();
for (let i = 0; i < buildings.length; i++) {
const height = buildings[i];
while (backStack.length && backStack[backStack.length - 1][1] <= height)
backStack.pop();
if (backStack.length) {
countArr[N - i - 1] += backStack.length;
if (
!closestArr[N - i - 1] ||
backStack[backStack.length - 1][0] - N + i + 1 <
closestArr[N - i - 1].dist
) {
closestArr[N - i - 1] = {
no: backStack[backStack.length - 1][0],
dist: backStack[backStack.length - 1][0] - N + i + 1,
};
}
}
backStack.push([N - i - 1, height]);
}
return countArr
.map((v, idx) => (v === 0 ? v : `${v} ${closestArr[idx].no + 1}`))
.join('\n');
};
console.log(solution(N, buildings));추후 작성 예정Reference
この問題について([伯俊]塔#22866を見て), 我々は、より多くの情報をここで見つけました https://velog.io/@ahu8867/백준-탑-보기-22866テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol