瀹炴椂浜ら€氳拷韪郴缁熻璁★細浠庨浂鏋勫缓鏅鸿兘鍏氦瀹氫綅鍣?/h1>

涓€銆侀棶棰樿儗鏅笌闇€姹傚垎鏋?/h2>

鍦ㄧ幇浠ｆ櫤鎱у煄甯傚缓璁句腑锛?strong>瀹炴椂鍏叡浜ら€氳拷韪郴缁?/strong>鏄彁鍗囧競姘戝嚭琛屼綋楠岀殑鍏抽敭鍩虹璁炬柦銆傛湰鏂囧皢鎺㈣濡備綍璁捐涓€涓珮鏁堢殑浜ら€氳拷韪ā鍧楋紝鏀寔浠ヤ笅鏍稿績鍔熻兘锛?/p>

• 绾胯矾绔欑偣绠＄悊锛氱淮鎶ゆ湁搴忕殑绔欑偣搴忓垪锛屾敮鎸佸崟鍚戣椹剁殑鍏氦绾胯矾
• 杞﹁締浣嶇疆鏌ヨ锛氭牴鎹溅杈嗙紪鍙峰揩閫熻幏鍙栧綋鍓嶆墍鍦ㄧ珯鐐?/li>
• 鏈€杩戣溅杈嗚绠?/strong>锛氳绠椾换鎰忕珯鐐硅窛绂绘渶杩戞潵杞﹁繕鏈夊嚑绔?/li>

浜屻€佹牳蹇冩暟鎹粨鏋勮璁?/h2>

涓轰簡瀹炵幇O(1)鏃堕棿澶嶆潅搴︾殑鏌ヨ鏁堢巼锛屾垜浠渶瑕佸阀濡欏湴閫夋嫨鏁版嵁缁撴瀯锛?/p>

2.1 绔欑偣绱㈠紩鏄犲皠

浣跨敤HashMap寤虹珛绔欑偣鍚嶇О鍒颁綅缃储寮曠殑鍙屽悜鏄犲皠锛岃繖鏍峰彲浠ュ湪甯告暟鏃堕棿鍐呭畬鎴愮珯鐐瑰畾浣嶏細

class TransitTracker {
    private stationIndex: Map<string, number>;  // 绔欑偣鍚?-> 浣嶇疆绱㈠紩
    private stationList: string[];               // 绱㈠紩 -> 绔欑偣鍚?
    private vehiclePositions: Map<number, string>; // 杞﹁締ID -> 褰撳墠绔欑偣
    private nearestDistance: number[];           // 棰勫鐞嗭細姣忕珯鍒版渶杩戣溅杈嗙殑璺濈
    
    constructor(routeString: string, vehicleLocations: Record<number, string>) {
        // 瑙ｆ瀽绾胯矾瀛楃涓诧紝寤虹珛绱㈠紩
        this.stationList = routeString.split('-');
        this.stationIndex = new Map();
        
        this.stationList.forEach((station, idx) => {
            this.stationIndex.set(station, idx);
        });
        
        // 瀛樺偍杞﹁締浣嶇疆
        this.vehiclePositions = new Map(Object.entries(vehicleLocations)
            .map(([id, station]) => [parseInt(id), station]));
        
        // 棰勫鐞嗘渶杩戣溅杈嗚窛绂?
        this.preprocessNearestVehicle();
    }
}

2.2 璺濈棰勫鐞嗙畻娉?/h3>

鍏抽敭浼樺寲鍦ㄤ簬浠庡彸鍚戝乏鎵弿锛岄鍏堣绠楁瘡涓珯鐐瑰埌鏈€杩戞潵杞︾殑璺濈锛?/p>

private preprocessNearestVehicle(): void {
    const n = this.stationList.length;
    this.nearestDistance = new Array(n).fill(-1);
    
    // 鏀堕泦鎵€鏈夎溅杈嗘墍鍦ㄧ珯鐐圭殑绱㈠紩
    const vehicleIndices: number[] = [];
    for (const station of this.vehiclePositions.values()) {
        const idx = this.stationIndex.get(station);
        if (idx !== undefined) {
            vehicleIndices.push(idx);
        }
    }
    
    // 浠庡彸鍚戝乏鎵弿锛岀淮鎶ゆ渶杩戣溅杈嗚窛绂?
    let minDistFromRight = Infinity;
    
    for (let i = n - 1; i >= 0; i--) {
        // 妫€鏌ュ綋鍓嶇珯鐐规槸鍚︽湁杞﹁締
        if (vehicleIndices.includes(i)) {
            minDistFromRight = 0;
        }
        
        if (minDistFromRight !== Infinity) {
            this.nearestDistance[i] = minDistFromRight;
        }
        minDistFromRight++;
    }
}

馃挕 浼樺寲鎻愮ず锛?/strong>棰勫鐞嗗悗锛?code>nearestToStation()鏌ヨ鐨勬椂闂村鏉傚害闄嶄负O(1)锛岄潪甯搁€傚悎楂橀鏌ヨ鍦烘櫙銆?

涓夈€丄PI鎺ュ彛瀹炵幇

3.1 鏌ヨ鏈€杩戣溅杈嗚窛绂?/h3>

getNearestVehicleDistance(stationName: string): number {
    const idx = this.stationIndex.get(stationName);
    if (idx === undefined) return -1;
    return this.nearestDistance[idx];
}

// 绀轰緥璋冪敤
// 绾胯矾: "涓灭珯-涓績骞垮満-绉戞妧鍥?澶у鍩?缁堢偣绔?
// 杞﹁締浣嶇疆: {101: "涓績骞垮満", 102: "澶у鍩?}

tracker.getNearestVehicleDistance("涓灭珯");     // -1 (鍓嶆柟鏃犺溅)
tracker.getNearestVehicleDistance("涓績骞垮満"); // 0  (褰撳墠绔欐湁杞?
tracker.getNearestVehicleDistance("绉戞妧鍥?);   // 1  (璺濇渶杩戣溅1绔?

3.2 鏌ヨ杞﹁締褰撳墠浣嶇疆

getVehicleLocation(vehicleId: number): string {
    return this.vehiclePositions.get(vehicleId) || "";
}

鍥涖€佸鏉傚害鍒嗘瀽

鎿嶄綔	鏃堕棿澶嶆潅搴?/th>	绌洪棿澶嶆潅搴?/th>
鍒濆鍖?/td>	O(n + m)	O(n + m)
鏌ヨ鏈€杩戣溅杈?/td>	O(1)	O(1)
鏌ヨ杞﹁締浣嶇疆	O(1)	O(1)

鍏朵腑 n 涓虹珯鐐规暟閲忥紝m 涓鸿溅杈嗘暟閲?/em>

浜斻€佹墿灞曟€濊€?/h2>

鈿狅笍 闈㈣瘯杩涢樁闂锛?/strong>

• 濡備綍鏀寔杞﹁締浣嶇疆鐨勫姩鎬佹洿鏂帮紵锛堝閲忔洿鏂伴澶勭悊鏁扮粍锛?/li>
• 濡備綍鎵╁睍鍒板弻鍚戣椹剁殑绾胯矾锛燂紙缁存姢涓や釜鏂瑰悜鐨勮窛绂绘暟缁勶級
• 濡備綍澶勭悊鐜舰绾胯矾锛燂紙鍙栨ā杩愮畻澶勭悊寰幆锛?/li>

鍏€佹€荤粨

鏈枃浠嬬粛鐨?strong>瀹炴椂浜ら€氳拷韪郴缁?/strong>璁捐鏂规锛岄€氳繃鍝堝笇鏄犲皠鍜岄澶勭悊鎶€鏈紝瀹炵幇浜嗛珮鏁堢殑杞﹁締瀹氫綅鍜岃窛绂绘煡璇㈠姛鑳姐€傛牳蹇冭鐐瑰寘鎷細

1. 浣跨敤鍙屽悜鏄犲皠蹇€熷畾浣嶇珯鐐?/li>
2. 浠庡彸鍚戝乏鎵弿棰勫鐞嗘渶杩戣窛绂?/li>
3. 绌洪棿鎹㈡椂闂达紝瀹炵幇O(1)鏌ヨ

系统设计 数据结构 哈希表 预处理优化 面试辅助 VO辅助 VO代面 算法面试 鎶€鏈潰璇?/span>