296 lines
13 KiB
HTML
296 lines
13 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>014. 合并区间 – 图解</title>
|
|||
|
|
<link rel="stylesheet" href="../shared/style.css">
|
|||
|
|
<style>
|
|||
|
|
.vis-area { min-height: 180px; padding: 16px 0; }
|
|||
|
|
.code-section { margin-top: 16px; }
|
|||
|
|
.interval-bar {
|
|||
|
|
height: 28px; border-radius: 6px; position: relative;
|
|||
|
|
display: inline-block; vertical-align: middle;
|
|||
|
|
transition: all 0.25s ease; min-width: 4px;
|
|||
|
|
}
|
|||
|
|
.interval-bar.merged { background: #dcfce7; border: 2px solid #16a34a; }
|
|||
|
|
.interval-bar.current { background: #dbeafe; border: 2px solid #3b82f6; }
|
|||
|
|
.interval-bar.checking { background: #fef3c7; border: 2px solid #f59e0b; }
|
|||
|
|
.interval-bar.new-merged { background: #bbf7d0; border: 2px solid #16a34a; box-shadow: 0 0 0 3px rgba(22,163,74,0.2); }
|
|||
|
|
.interval-row { display: flex; align-items: center; gap: 8px; margin: 6px 0; font-size: 13px; }
|
|||
|
|
.interval-label { min-width: 60px; text-align: right; color: #475569; font-weight: 600; }
|
|||
|
|
.axis-line { height: 2px; background: #94a3b8; position: relative; margin: 4px 0 20px; border-radius: 1px; }
|
|||
|
|
.axis-tick { position: absolute; bottom: -18px; transform: translateX(-50%); font-size: 11px; color: #64748b; font-family: monospace; }
|
|||
|
|
.axis-tick::before { content: ''; position: absolute; top: -8px; left: 50%; width: 1px; height: 6px; background: #94a3b8; }
|
|||
|
|
.result-badge { display: inline-block; padding: 3px 10px; border-radius: 8px; font-size: 13px; font-weight: 600; margin: 3px; }
|
|||
|
|
.result-badge.green { background: #dcfce7; color: #166534; }
|
|||
|
|
.result-badge.blue { background: #dbeafe; color: #1e40af; }
|
|||
|
|
.legend { display: flex; gap: 14px; margin: 8px 0; font-size: 12px; flex-wrap: wrap; }
|
|||
|
|
.legend span { display: inline-flex; align-items: center; gap: 4px; }
|
|||
|
|
.legend .dot { width: 12px; height: 12px; border-radius: 3px; display: inline-block; }
|
|||
|
|
</style>
|
|||
|
|
</head>
|
|||
|
|
<body>
|
|||
|
|
<div class="container">
|
|||
|
|
<h1>🟡 014. 合并区间 <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" placeholder="默认示例，可自定义">
|
|||
|
|
<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 = [
|
|||
|
|
{input:[[1,3],[2,6],[8,10],[15,18]], label:'示例1: [[1,3],[2,6],[8,10],[15,18]]'},
|
|||
|
|
{input:[[1,4],[4,5]], label:'示例2: [[1,4],[4,5]]'},
|
|||
|
|
{input:[[1,4],[0,4]], label:'示例3: [[1,4],[0,4]]'},
|
|||
|
|
{input:[[1,4],[2,3]], label:'包含: [[1,4],[2,3]]'},
|
|||
|
|
];
|
|||
|
|
let intervals, steps, stepCtrl;
|
|||
|
|
|
|||
|
|
function buildSteps(raw) {
|
|||
|
|
intervals = [...raw].sort((a,b) => a[0] - b[0]);
|
|||
|
|
steps = [];
|
|||
|
|
const result = [];
|
|||
|
|
let cur = intervals[0];
|
|||
|
|
|
|||
|
|
steps.push({
|
|||
|
|
stage:'sort', curIdx:-1, checkIdx:-1,
|
|||
|
|
sorted: intervals.map(x=>[...x]),
|
|||
|
|
cur: [...cur], result: [],
|
|||
|
|
msg:`按左端点排序: ${JSON.stringify(raw)} → ${JSON.stringify(intervals)}`
|
|||
|
|
});
|
|||
|
|
|
|||
|
|
steps.push({
|
|||
|
|
stage:'init', curIdx:0, checkIdx:-1,
|
|||
|
|
sorted: intervals.map(x=>[...x]),
|
|||
|
|
cur: [...cur], result: [],
|
|||
|
|
msg:`初始化：当前合并区间 = [${cur[0]},${cur[1]}]`
|
|||
|
|
});
|
|||
|
|
|
|||
|
|
for (let i = 1; i < intervals.length; i++) {
|
|||
|
|
const next = intervals[i];
|
|||
|
|
steps.push({
|
|||
|
|
stage:'check', curIdx:i-1, checkIdx:i,
|
|||
|
|
sorted: intervals.map(x=>[...x]),
|
|||
|
|
cur: [...cur], result: JSON.parse(JSON.stringify(result)),
|
|||
|
|
msg:`比较：当前合并区间 [${cur[0]},${cur[1]}] 与 [${next[0]},${next[1]}]`
|
|||
|
|
});
|
|||
|
|
|
|||
|
|
if (next[0] <= cur[1]) {
|
|||
|
|
const oldEnd = cur[1];
|
|||
|
|
cur[1] = Math.max(cur[1], next[1]);
|
|||
|
|
steps.push({
|
|||
|
|
stage:'merge', curIdx:i-1, checkIdx:i,
|
|||
|
|
sorted: intervals.map(x=>[...x]),
|
|||
|
|
cur: [...cur], result: JSON.parse(JSON.stringify(result)),
|
|||
|
|
msg:`重叠！next[0]=${next[0]} ≤ cur[1]=${oldEnd}，合并 → [${cur[0]},${cur[1]}]`
|
|||
|
|
});
|
|||
|
|
} else {
|
|||
|
|
result.push([...cur]);
|
|||
|
|
steps.push({
|
|||
|
|
stage:'no_overlap', curIdx:i-1, checkIdx:i,
|
|||
|
|
sorted: intervals.map(x=>[...x]),
|
|||
|
|
cur: [...cur], result: JSON.parse(JSON.stringify(result)),
|
|||
|
|
msg:`不重叠：next[0]=${next[0]} > cur[1]=${cur[1]}，保存 [${cur[0]},${cur[1]}]`
|
|||
|
|
});
|
|||
|
|
cur = [...next];
|
|||
|
|
steps.push({
|
|||
|
|
stage:'next', curIdx:i, checkIdx:-1,
|
|||
|
|
sorted: intervals.map(x=>[...x]),
|
|||
|
|
cur: [...cur], result: JSON.parse(JSON.stringify(result)),
|
|||
|
|
msg:`新的当前合并区间 = [${cur[0]},${cur[1]}]`
|
|||
|
|
});
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
result.push([...cur]);
|
|||
|
|
steps.push({
|
|||
|
|
stage:'done', curIdx:-1, checkIdx:-1,
|
|||
|
|
sorted: intervals.map(x=>[...x]),
|
|||
|
|
cur: [...cur], result: JSON.parse(JSON.stringify(result)),
|
|||
|
|
msg:`保存最后一个区间 [${cur[0]},${cur[1]}]，合并完毕，共 ${result.length} 个区间`
|
|||
|
|
});
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function renderIntervalBar(interval, minVal, maxVal, totalWidth, cls) {
|
|||
|
|
const range = maxVal - minVal || 1;
|
|||
|
|
const left = ((interval[0] - minVal) / range) * totalWidth;
|
|||
|
|
const width = Math.max(4, ((interval[1] - interval[0]) / range) * totalWidth);
|
|||
|
|
return `<span class="interval-bar ${cls}" style="margin-left:${left}px;width:${width}px;" title="[${interval[0]},${interval[1]}]"></span>`;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function render(stepIdx) {
|
|||
|
|
const s = steps[stepIdx];
|
|||
|
|
const sorted = s.sorted;
|
|||
|
|
if (!sorted || sorted.length === 0) return;
|
|||
|
|
|
|||
|
|
// Find axis range
|
|||
|
|
let minVal = Infinity, maxVal = -Infinity;
|
|||
|
|
sorted.forEach(iv => { minVal = Math.min(minVal, iv[0]); maxVal = Math.max(maxVal, iv[1]); });
|
|||
|
|
if (s.result) s.result.forEach(iv => { minVal = Math.min(minVal, iv[0]); maxVal = Math.max(maxVal, iv[1]); });
|
|||
|
|
if (s.cur) { minVal = Math.min(minVal, s.cur[0]); maxVal = Math.max(maxVal, s.cur[1]); }
|
|||
|
|
minVal = Math.min(minVal, 0); maxVal = maxVal + 1;
|
|||
|
|
|
|||
|
|
const totalWidth = Math.min(680, window.innerWidth - 160);
|
|||
|
|
|
|||
|
|
let viz = '<div class="legend">';
|
|||
|
|
viz += '<span><span class="dot" style="background:#dbeafe;border:2px solid #3b82f6;"></span>当前合并区间</span>';
|
|||
|
|
viz += '<span><span class="dot" style="background:#fef3c7;border:2px solid #f59e0b;"></span>待比较</span>';
|
|||
|
|
viz += '<span><span class="dot" style="background:#dcfce7;border:2px solid #16a34a;"></span>已合并结果</span>';
|
|||
|
|
viz += '</div>';
|
|||
|
|
|
|||
|
|
// Draw sorted intervals as rows
|
|||
|
|
viz += '<div style="background:#f8fafc;border-radius:12px;padding:12px;position:relative;">';
|
|||
|
|
sorted.forEach((iv, i) => {
|
|||
|
|
let cls = '';
|
|||
|
|
if (s.result) {
|
|||
|
|
const isMerged = s.result.some(r => r[0] === iv[0] && r[1] === iv[1]);
|
|||
|
|
if (isMerged) cls = 'merged';
|
|||
|
|
}
|
|||
|
|
if (s.cur && s.cur[0] === iv[0] && s.cur[1] === iv[1]) cls = 'current';
|
|||
|
|
if (s.checkIdx === i) cls = 'checking';
|
|||
|
|
if (s.stage === 'merge' && s.checkIdx === i) cls = 'new-merged';
|
|||
|
|
|
|||
|
|
viz += '<div class="interval-row">';
|
|||
|
|
viz += `<span class="interval-label">${i+1}.</span>`;
|
|||
|
|
viz += `<span style="color:#64748b;font-family:monospace;min-width:70px;">[${iv[0]},${iv[1]}]</span>`;
|
|||
|
|
viz += `<div style="flex:1;position:relative;height:28px;">`;
|
|||
|
|
viz += renderIntervalBar(iv, minVal, maxVal, totalWidth, cls);
|
|||
|
|
viz += '</div></div>';
|
|||
|
|
});
|
|||
|
|
|
|||
|
|
// Axis
|
|||
|
|
viz += '<div class="axis-line" style="width:' + totalWidth + 'px;margin-left:' + ((sorted[0][0] - minVal) / (maxVal - minVal) * totalWidth) + 'px;">';
|
|||
|
|
const tickStep = Math.max(1, Math.ceil((maxVal - minVal) / 10));
|
|||
|
|
for (let v = Math.ceil(minVal); v <= maxVal; v += tickStep) {
|
|||
|
|
const pos = ((v - minVal) / (maxVal - minVal)) * totalWidth;
|
|||
|
|
viz += `<span class="axis-tick" style="left:${pos}px;">${v}</span>`;
|
|||
|
|
}
|
|||
|
|
viz += '</div>';
|
|||
|
|
viz += '</div>';
|
|||
|
|
|
|||
|
|
// Merged result preview
|
|||
|
|
if (s.result && s.result.length > 0) {
|
|||
|
|
viz += '<div style="margin-top:12px;font-size:13px;color:#475569;"><b>已合并结果：</b>';
|
|||
|
|
s.result.forEach(r => { viz += `<span class="result-badge green">[${r[0]},${r[1]}]</span>`; });
|
|||
|
|
viz += '</div>';
|
|||
|
|
}
|
|||
|
|
if (s.cur && s.stage !== 'done') {
|
|||
|
|
viz += `<div style="margin-top:6px;font-size:13px;color:#475569;"><b>当前合并中：</b><span class="result-badge blue">[${s.cur[0]},${s.cur[1]}]</span></div>`;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
$('vizArea').innerHTML = viz;
|
|||
|
|
|
|||
|
|
// Detail
|
|||
|
|
let detail = '<div class="calc-block">' + s.msg + '</div>';
|
|||
|
|
if (s.stage === 'check' || s.stage === 'merge') {
|
|||
|
|
detail += `<div class="formula-box">判断条件：<code>next[0] ≤ cur[1]</code> → ${s.checkIdx >= 0 ? sorted[s.checkIdx][0] : '?'} ${s.stage==='merge' ? '≤' : '>'} ${s.cur ? s.cur[1] : '?'}</div>`;
|
|||
|
|
}
|
|||
|
|
$('detailContent').innerHTML = detail;
|
|||
|
|
|
|||
|
|
if (s.stage === 'done') {
|
|||
|
|
let res = '<div class="final-answer">合并结果：<b>' + JSON.stringify(s.result) + '</b>';
|
|||
|
|
res += `<br>共 ${s.result.length} 个区间`;
|
|||
|
|
res += '<div class="complexity">时间复杂度 O(n log n)（排序） ｜ 空间复杂度 O(n) ｜ 贪心策略</div>';
|
|||
|
|
res += '</div>';
|
|||
|
|
$('resultContent').innerHTML = res;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
$('hintText').textContent = s.msg;
|
|||
|
|
|
|||
|
|
const stages = [['sort','排序'],['init','初始化'],['check','比较'],['merge','合并'],['no_overlap','不重叠'],['next','新区间'],['done','完成']];
|
|||
|
|
$('pipeline').innerHTML = stages.map(([k,l]) =>
|
|||
|
|
`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`
|
|||
|
|
).join('<i>→</i>');
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function init() {
|
|||
|
|
const sel = $('exampleSelect');
|
|||
|
|
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
|||
|
|
$('inputArea').value = JSON.stringify(examples[0].input);
|
|||
|
|
buildSteps(examples[0].input);
|
|||
|
|
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 = () => {
|
|||
|
|
try {
|
|||
|
|
const arr = JSON.parse($('inputArea').value);
|
|||
|
|
if (!Array.isArray(arr) || arr.length === 0) throw new Error();
|
|||
|
|
arr.forEach(iv => { if (!Array.isArray(iv) || iv.length !== 2) throw new Error(); });
|
|||
|
|
buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
|||
|
|
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
|||
|
|
} catch(e) { alert('请输入合法区间数组，例如 [[1,3],[2,6],[8,10],[15,18]]'); }
|
|||
|
|
};
|
|||
|
|
$('exampleSelect').onchange = () => {
|
|||
|
|
const e = examples[parseInt($('exampleSelect').value)];
|
|||
|
|
$('inputArea').value = JSON.stringify(e.input);
|
|||
|
|
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
|||
|
|
};
|
|||
|
|
$('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(`def merge(intervals):
|
|||
|
|
intervals.sort(key=lambda x: x[0])
|
|||
|
|
merged = [intervals[0]]
|
|||
|
|
for i in range(1, len(intervals)):
|
|||
|
|
if intervals[i][0] <= merged[-1][1]:
|
|||
|
|
merged[-1][1] = max(merged[-1][1], intervals[i][1])
|
|||
|
|
else:
|
|||
|
|
merged.append(intervals[i])
|
|||
|
|
return merged`, {lang:'Python'});
|
|||
|
|
})();
|
|||
|
|
</script>
|
|||
|
|
</body>
|
|||
|
|
</html>
|