274 lines
11 KiB
HTML
274 lines
11 KiB
HTML
|
<!DOCTYPE html>
|
|||
|
|
<html lang="zh-Hans">
|
|||
|
|
<head>
|
|||
|
|
<meta charset="UTF-8">
|
|||
|
|
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
|||
|
|
<title>074. 数组中的第K个最大元素 – 图解</title>
|
|||
|
|
<link rel="stylesheet" href="../shared/style.css">
|
|||
|
|
<style>
|
|||
|
|
.vis-area { min-height: 120px; padding: 16px 0; }
|
|||
|
|
.code-section { margin-top: 16px; }
|
|||
|
|
.heap-row { display:flex; justify-content:center; gap:6px; margin:6px 0; flex-wrap:wrap; }
|
|||
|
|
.heap-cell {
|
|||
|
|
min-width:36px; height:32px; display:inline-flex; align-items:center; justify-content:center;
|
|||
|
|
border-radius:8px; font-weight:700; font-size:14px; font-family:monospace;
|
|||
|
|
transition: all 0.25s ease; padding:2px 8px;
|
|||
|
|
}
|
|||
|
|
.heap-cell.default { background:#e2e8f0; color:#0f172a; }
|
|||
|
|
.heap-cell.top { background:#fef3c7; color:#92400e; border:2px solid #f59e0b; box-shadow:0 0 0 3px rgba(245,158,11,0.2); }
|
|||
|
|
.heap-cell.new { background:#dcfce7; color:#166534; border:2px solid #16a34a; }
|
|||
|
|
.heap-cell.ejected { background:#fee2e2; color:#991b1b; border:2px dashed #ef4444; opacity:0.5; }
|
|||
|
|
.heap-cell.in-heap { background:#dbeafe; color:#1e40af; border:1px solid #3b82f6; }
|
|||
|
|
.arrow-down { text-align:center; color:#94a3b8; font-size:18px; margin:2px 0; }
|
|||
|
|
</style>
|
|||
|
|
</head>
|
|||
|
|
<body>
|
|||
|
|
<div class="container">
|
|||
|
|
<h1>🟡 074. 数组中的第K个最大元素 <span class="badge medium">中等</span></h1>
|
|||
|
|
<p class="subtitle">分类：堆 ｜ LeetCode Hot 100</p>
|
|||
|
|
|
|||
|
|
<div class="controls" id="controls">
|
|||
|
|
<label for="inputArea">输入：</label>
|
|||
|
|
<input type="text" id="inputArea" value="nums=[3,2,1,5,6,4], k=2" placeholder="nums=[...], k=N">
|
|||
|
|
<button id="applyBtn" class="primary">生成图解</button>
|
|||
|
|
<select id="exampleSelect"></select>
|
|||
|
|
<span style="flex:1"></span>
|
|||
|
|
<button id="prevBtn">◀ 上一步</button>
|
|||
|
|
<button id="nextBtn">下一步 ▶</button>
|
|||
|
|
<button id="jumpBtn">⏭ 跳到结果</button>
|
|||
|
|
<button id="autoBtn">自动播放</button>
|
|||
|
|
<button id="resetBtn">重置</button>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<div class="pipeline" id="pipeline"></div>
|
|||
|
|
|
|||
|
|
<div class="hint info" id="hintBox">
|
|||
|
|
<span id="stepInfo"></span><br>
|
|||
|
|
<span id="hintText"></span>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<div class="panels">
|
|||
|
|
<div class="panel" id="mainPanel">
|
|||
|
|
<h3>📊 可视化</h3>
|
|||
|
|
<div class="vis-area" id="vizArea">点击「生成图解」开始</div>
|
|||
|
|
</div>
|
|||
|
|
<div class="panel-grid">
|
|||
|
|
<div class="panel" id="detailPanel">
|
|||
|
|
<h3>📝 当前步骤详情</h3>
|
|||
|
|
<div id="detailContent">等待开始...</div>
|
|||
|
|
</div>
|
|||
|
|
<div class="panel" id="resultPanel">
|
|||
|
|
<h3>✅ 结果</h3>
|
|||
|
|
<div id="resultContent">等待完成...</div>
|
|||
|
|
</div>
|
|||
|
|
</div>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<div class="panel code-section">
|
|||
|
|
<h3>💻 参考代码（Python）</h3>
|
|||
|
|
<div id="codeArea"></div>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<footer>Powered by QwenPaw · 图解算法 · LeetCode Hot 100</footer>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<script src="../shared/algo-viz.js"></script>
|
|||
|
|
<script>
|
|||
|
|
"use strict";
|
|||
|
|
(function() {
|
|||
|
|
const examples = [
|
|||
|
|
{nums:[3,2,1,5,6,4], k:2, label:'示例1: [3,2,1,5,6,4], k=2'},
|
|||
|
|
{nums:[3,2,3,1,2,4,5,5,6], k:4, label:'示例2: [3,2,3,1,2,4,5,5,6], k=4'},
|
|||
|
|
];
|
|||
|
|
|
|||
|
|
let nums, k, steps, stepCtrl;
|
|||
|
|
|
|||
|
|
// Min-heap utilities
|
|||
|
|
function heapPush(heap, val) {
|
|||
|
|
heap.push(val);
|
|||
|
|
let i = heap.length - 1;
|
|||
|
|
while (i > 0) {
|
|||
|
|
const parent = (i - 1) >> 1;
|
|||
|
|
if (heap[parent] > heap[i]) {
|
|||
|
|
[heap[parent], heap[i]] = [heap[i], heap[parent]];
|
|||
|
|
i = parent;
|
|||
|
|
} else break;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
function heapPop(heap) {
|
|||
|
|
const top = heap[0];
|
|||
|
|
const last = heap.pop();
|
|||
|
|
if (heap.length > 0) {
|
|||
|
|
heap[0] = last;
|
|||
|
|
let i = 0;
|
|||
|
|
while (true) {
|
|||
|
|
let smallest = i;
|
|||
|
|
const l = 2*i+1, r = 2*i+2;
|
|||
|
|
if (l < heap.length && heap[l] < heap[smallest]) smallest = l;
|
|||
|
|
if (r < heap.length && heap[r] < heap[smallest]) smallest = r;
|
|||
|
|
if (smallest !== i) { [heap[i], heap[smallest]] = [heap[smallest], heap[i]]; i = smallest; }
|
|||
|
|
else break;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
return top;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function buildSteps(arr, kVal) {
|
|||
|
|
nums = arr.slice(); k = kVal;
|
|||
|
|
steps = [];
|
|||
|
|
|
|||
|
|
// Stage 1: Show initial array
|
|||
|
|
steps.push({stage:'init', msg:`输入数组长度=${arr.length}，找第 ${k} 大元素。用小顶堆维护前 K 大：堆顶 = 当前第 K 大`, arrHL:{}, heap:[], idx:-1, popped:null});
|
|||
|
|
|
|||
|
|
// Stage 2: Build initial heap with first k elements
|
|||
|
|
const heap = [];
|
|||
|
|
for (let i = 0; i < kVal; i++) {
|
|||
|
|
heapPush(heap, arr[i]);
|
|||
|
|
const arrHL = {};
|
|||
|
|
for (let j = 0; j <= i; j++) arrHL[j] = 'blue';
|
|||
|
|
steps.push({stage:'build', msg:`将 nums[${i}]=${arr[i]} 加入小顶堆，堆大小=${heap.length}`, arrHL, heap:heap.slice(), idx:i, popped:null});
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
steps.push({stage:'heap-ready', msg:`初始小顶堆构建完成，堆顶=${heap[0]} 即当前第 ${k} 大`, arrHL:{}, heap:heap.slice(), idx:-1, popped:null});
|
|||
|
|
|
|||
|
|
// Stage 3: Process remaining elements
|
|||
|
|
for (let i = kVal; i < arr.length; i++) {
|
|||
|
|
const arrHL = {};
|
|||
|
|
// Mark heap elements blue, current element orange
|
|||
|
|
for (let j = 0; j < kVal; j++) arrHL[j] = 'blue';
|
|||
|
|
arrHL[i] = 'orange';
|
|||
|
|
steps.push({stage:'compare', msg:`检查 nums[${i}]=${arr[i]}，与堆顶 ${heap[0]} 比较`, arrHL, heap:heap.slice(), idx:i, popped:null});
|
|||
|
|
|
|||
|
|
if (arr[i] > heap[0]) {
|
|||
|
|
const popped = heapPop(heap);
|
|||
|
|
heapPush(heap, arr[i]);
|
|||
|
|
const arrHL2 = {};
|
|||
|
|
for (let j = 0; j < kVal; j++) arrHL2[j] = 'blue';
|
|||
|
|
arrHL2[i] = 'green';
|
|||
|
|
steps.push({stage:'replace', msg:`${arr[i]} > ${popped}，弹出堆顶 ${popped}，压入 ${arr[i]}，新堆顶=${heap[0]}`, arrHL:arrHL2, heap:heap.slice(), idx:i, popped});
|
|||
|
|
} else {
|
|||
|
|
const arrHL2 = {};
|
|||
|
|
for (let j = 0; j < kVal; j++) arrHL2[j] = 'blue';
|
|||
|
|
arrHL2[i] = 'red';
|
|||
|
|
steps.push({stage:'skip', msg:`${arr[i]} ≤ ${heap[0]}，跳过，堆不变`, arrHL:arrHL2, heap:heap.slice(), idx:i, popped:null});
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// Stage 4: Result
|
|||
|
|
steps.push({stage:'done', msg:`遍历结束，小顶堆堆顶 ${heap[0]} 即为第 ${k} 大元素`, arrHL:{}, heap:heap.slice(), idx:-1, popped:null, result:heap[0]});
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function renderHeap(heap, topHighlight) {
|
|||
|
|
if (heap.length === 0) return '<div style="color:#94a3b8;font-style:italic;">空堆</div>';
|
|||
|
|
let html = '<div style="text-align:center;padding:8px 0;">';
|
|||
|
|
// Level order display
|
|||
|
|
let level = 0, idx = 0;
|
|||
|
|
while (idx < heap.length) {
|
|||
|
|
const count = Math.pow(2, level);
|
|||
|
|
html += '<div class="heap-row">';
|
|||
|
|
for (let j = 0; j < count && idx < heap.length; j++, idx++) {
|
|||
|
|
let cls = 'in-heap';
|
|||
|
|
if (idx === 0 && topHighlight) cls = 'top';
|
|||
|
|
html += `<span class="heap-cell ${cls}">${heap[idx]}</span>`;
|
|||
|
|
}
|
|||
|
|
html += '</div>';
|
|||
|
|
if (idx < heap.length) html += '<div class="arrow-down">↓</div>';
|
|||
|
|
level++;
|
|||
|
|
}
|
|||
|
|
html += '</div>';
|
|||
|
|
return html;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function render(step) {
|
|||
|
|
const s = steps[step];
|
|||
|
|
|
|||
|
|
// Main visualization
|
|||
|
|
let viz = '<div style="margin-bottom:12px;"><b>原始数组：</b></div>';
|
|||
|
|
viz += renderArray(nums, {highlights: s.arrHL});
|
|||
|
|
if (s.popped !== null) {
|
|||
|
|
viz += `<div style="margin-top:8px;color:#991b1b;">弹出: <span class="heap-cell ejected" style="display:inline-flex;min-width:30px;">${s.popped}</span></div>`;
|
|||
|
|
}
|
|||
|
|
viz += '<div style="margin:12px 0;"><b>小顶堆 (size=' + s.heap.length + ')：</b></div>';
|
|||
|
|
viz += renderHeap(s.heap, s.stage === 'heap-ready' || s.stage === 'done');
|
|||
|
|
if (s.heap.length > 0) {
|
|||
|
|
viz += `<div style="margin-top:6px;font-size:13px;color:#64748b;">堆顶(最小值) = <code>${s.heap[0]}</code></div>`;
|
|||
|
|
}
|
|||
|
|
$('vizArea').innerHTML = viz;
|
|||
|
|
|
|||
|
|
// Detail
|
|||
|
|
let detail = '<div class="calc-block">' + s.msg + '</div>';
|
|||
|
|
if (s.stage === 'compare') {
|
|||
|
|
detail += `<div style="margin-top:8px;">比较: nums[${s.idx}]=<b>${nums[s.idx]}</b> vs 堆顶=<b>${s.heap[0]}</b></div>`;
|
|||
|
|
}
|
|||
|
|
$('detailContent').innerHTML = detail;
|
|||
|
|
|
|||
|
|
// Result
|
|||
|
|
if (s.stage === 'done') {
|
|||
|
|
$('resultContent').innerHTML = `<div class="final-answer">第 <b>${k}</b> 大元素 = <b>${s.result}</b><br><br>小顶堆始终保持 K 个最大元素，堆顶即第 K 大。<br>时间 O(nlogk)，空间 O(k)</div>`;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
$('hintText').textContent = s.msg;
|
|||
|
|
|
|||
|
|
// Pipeline
|
|||
|
|
const stages = ['init→初始化','build→建堆','heap-ready→堆就绪','compare→比较','replace→替换','skip→跳过','done→完成'];
|
|||
|
|
$('pipeline').innerHTML = stages.map(st => {
|
|||
|
|
const [key, label] = st.split('→');
|
|||
|
|
return `<span class="pipe-step ${s.stage===key?'active':''}">${label}</span>`;
|
|||
|
|
}).join('<i>→</i>');
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function init() {
|
|||
|
|
const sel = $('exampleSelect');
|
|||
|
|
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
|||
|
|
|
|||
|
|
buildSteps(examples[0].nums, examples[0].k);
|
|||
|
|
stepCtrl = new StepController({onStep: render});
|
|||
|
|
stepCtrl.setSteps(steps.map((_,i) => i));
|
|||
|
|
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
|||
|
|
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
|||
|
|
|
|||
|
|
$('applyBtn').onclick = () => {
|
|||
|
|
const m = $('inputArea').value.match(/nums=\[([^\]]+)\]\s*,\s*k=(\d+)/);
|
|||
|
|
if (!m) { alert('格式: nums=[3,2,1,5,6,4], k=2'); return; }
|
|||
|
|
const arr = m[1].split(',').map(Number);
|
|||
|
|
const kVal = parseInt(m[2]);
|
|||
|
|
buildSteps(arr, kVal);
|
|||
|
|
stepCtrl.setSteps(steps.map((_,i) => i));
|
|||
|
|
render(0);
|
|||
|
|
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
|||
|
|
};
|
|||
|
|
$('exampleSelect').onchange = () => {
|
|||
|
|
const e = examples[parseInt($('exampleSelect').value)];
|
|||
|
|
$('inputArea').value = `nums=[${e.nums}], k=${e.k}`;
|
|||
|
|
buildSteps(e.nums, e.k);
|
|||
|
|
stepCtrl.setSteps(steps.map((_,i) => i));
|
|||
|
|
render(0);
|
|||
|
|
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
|||
|
|
};
|
|||
|
|
$('prevBtn').onclick = () => stepCtrl.prev();
|
|||
|
|
$('nextBtn').onclick = () => stepCtrl.next();
|
|||
|
|
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
|||
|
|
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
|||
|
|
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
|||
|
|
}
|
|||
|
|
init();
|
|||
|
|
|
|||
|
|
$('codeArea').innerHTML = renderCode(`import heapq
|
|||
|
|
|
|||
|
|
def findKthLargest(nums, k):
|
|||
|
|
# 用小顶堆维护前 K 大元素
|
|||
|
|
heap = []
|
|||
|
|
for num in nums:
|
|||
|
|
if len(heap) < k:
|
|||
|
|
heapq.heappush(heap, num) # 堆未满，直接加入
|
|||
|
|
elif num > heap[0]:
|
|||
|
|
heapq.heapreplace(heap, num) # 比堆顶大，替换堆顶
|
|||
|
|
return heap[0] # 堆顶即第 K 大
|
|||
|
|
|
|||
|
|
# 复杂度：O(n log k) 时间，O(k) 空间`, {lang:'Python'});
|
|||
|
|
|
|||
|
|
})();
|
|||
|
|
</script>
|
|||
|
|
</body>
|
|||
|
|
</html>
|