[伯俊]Skyline簡単な#1863

11956 ワード
1863 白駿 テキストリンク
説明:
この問題を見てstackを思い出すのがうらやましい...
最初は感覚が見つからなかったので、他の人の解答を見て、スタックを使わずにそのままhashmapでいいと思っていたので、解答しましたが、例testcaseに合格しただけで、残りは失敗しました.
hashmapを用いたプールは0に遭遇する前にy値をmapに入れ,passがなければその中に入れ,count+1で解く.これで次の問題が発生しました.
2244122の場合、ビルは2つ、4つ、1つ、2つ、合計4つですが、2から1回濾過して3つになります.スタックを使用する必要があります
stackもstackですが、ここでは単調stackのテクニックを使いました.
スタックが1つあるたびに、ビルの高さが高くなると、スタックに対応する高さを追加し、count+1します.
ビルを下に行くと、スタックに高さがポップアップされ、hashmapで解凍したときのエラーを防ぐことができます.
このような問題は、COTEEで出題されると、問題を解いた人だけが解けます
+そして他の人のc++解答を見て、以下のテクニックを学びました.
for (auto &[x, y] : V) cin >> x >> y;
Node.説明する
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const positions = input.slice(1).map((v) => v.split(' ').map(Number));

const solution = (N, positions) => {
  let count = 0;
  const stack = [];
  positions.forEach(([_, val]) => {
    while (stack.length && stack[stack.length - 1] > val) stack.pop();
    if (val && (stack.length === 0 || stack[stack.length - 1] < val))
      stack.push(val), count++;
  });
  return count;
};

console.log(solution(N, positions));
C++プール
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    vector<pair<int,int>> V(N);
    for (auto &[x, y] : V) cin >> x >> y;
    
    stack<int> S;
    int cnt = 0;
    for (auto &[_, y] : V) {
        while(S.size() && S.top() > y) S.pop();
        if (y && (S.empty() || S.top() < y)) {
            S.push(y);
            cnt+=1;
        }
    }
    cout << cnt << '\n';
    return 0;
}
閉鎖スコープとは?
コートリン7-1線形レイアウト