228 lines
9.4 KiB
HTML
228 lines
9.4 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>072. 每日温度 – 图解</title>
|
|||
|
|
<link rel="stylesheet" href="../shared/style.css">
|
|||
|
|
<style>
|
|||
|
|
.vis-area { min-height: 120px; padding: 16px 0; }
|
|||
|
|
.code-section { margin-top: 16px; }
|
|||
|
|
.temp-bar-container { display:flex; align-items:flex-end; gap:4px; height:140px; padding:8px; background:#f8fafc; border:1px solid var(--border); border-radius:8px; margin:8px 0; }
|
|||
|
|
.temp-bar-wrap { display:flex; flex-direction:column; align-items:center; gap:2px; flex:1; max-width:50px; }
|
|||
|
|
.temp-bar { width:100%; border-radius:4px 4px 0 0; transition:all 0.3s; min-height:4px; }
|
|||
|
|
.temp-label { font-size:11px; font-weight:600; }
|
|||
|
|
.wait-label { font-size:11px; color:var(--green); font-weight:700; min-height:16px; }
|
|||
|
|
.index-label { font-size:10px; color:var(--text-muted); }
|
|||
|
|
</style>
|
|||
|
|
</head>
|
|||
|
|
<body>
|
|||
|
|
<div class="container">
|
|||
|
|
<h1>🟡 072. 每日温度 <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="temperatures=[73,74,75,71,69,72,76,73]">
|
|||
|
|
<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 = [
|
|||
|
|
{temps:[73,74,75,71,69,72,76,73], label:'示例1: [73,74,75,71,69,72,76,73]'},
|
|||
|
|
{temps:[30,40,50,60], label:'示例2: 递增'},
|
|||
|
|
{temps:[30,60,90], label:'示例3: [30,60,90]'},
|
|||
|
|
];
|
|||
|
|
let temps, steps, stepCtrl;
|
|||
|
|
|
|||
|
|
function buildSteps(temperatures) {
|
|||
|
|
temps = temperatures;
|
|||
|
|
steps = [];
|
|||
|
|
const n = temperatures.length;
|
|||
|
|
const answer = new Array(n).fill(0);
|
|||
|
|
const stack = []; // indices
|
|||
|
|
|
|||
|
|
steps.push({stage:'init', msg:'初始化：单调栈为空，答案全为 0', currentIdx:-1, stack:[], answer:[...answer], currentTemp:null, poppedIdx:-1, matchIdx:-1});
|
|||
|
|
|
|||
|
|
// Find min and max for bar scaling
|
|||
|
|
const maxTemp = Math.max(...temperatures);
|
|||
|
|
const minTemp = Math.min(...temperatures);
|
|||
|
|
const range = maxTemp - minTemp || 1;
|
|||
|
|
|
|||
|
|
for (let i = 0; i < n; i++) {
|
|||
|
|
const t = temperatures[i];
|
|||
|
|
|
|||
|
|
// Pop while current temp > stack top temp
|
|||
|
|
while (stack.length > 0 && t > temperatures[stack[stack.length - 1]]) {
|
|||
|
|
const poppedIdx = stack.pop();
|
|||
|
|
answer[poppedIdx] = i - poppedIdx;
|
|||
|
|
steps.push({stage:'pop', msg:`T[${i}]=${t} > T[${poppedIdx}]=${temperatures[poppedIdx]}，弹出 ${poppedIdx}，answer[${poppedIdx}] = ${i}-${poppedIdx} = ${i-poppedIdx}`, currentIdx:i, stack:[...stack], answer:[...answer], currentTemp:t, poppedIdx, matchIdx:i});
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
if (stack.length > 0) {
|
|||
|
|
steps.push({stage:'push', msg:`T[${i}]=${t} ≤ T[${stack[stack.length-1]}]=${temperatures[stack[stack.length-1]]}，${t} 入栈等待更高温度`, currentIdx:i, stack:[...stack, i], answer:[...answer], currentTemp:t, poppedIdx:-1, matchIdx:-1});
|
|||
|
|
} else {
|
|||
|
|
steps.push({stage:'push', msg:`T[${i}]=${t}，栈为空或栈顶更大，${t} 入栈`, currentIdx:i, stack:[...stack, i], answer:[...answer], currentTemp:t, poppedIdx:-1, matchIdx:-1});
|
|||
|
|
}
|
|||
|
|
stack.push(i);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// Remaining in stack have answer 0
|
|||
|
|
if (stack.length > 0) {
|
|||
|
|
steps.push({stage:'remaining', msg:`遍历完毕，栈中剩余 [${stack.join(',')}] 的答案均为 0（之后没有更高温度）`, currentIdx:-1, stack:[...stack], answer:[...answer], currentTemp:null, poppedIdx:-1, matchIdx:-1});
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
steps.push({stage:'done', msg:`结果：[${answer.join(', ')}]`, currentIdx:-1, stack:[], answer:[...answer], currentTemp:null, poppedIdx:-1, matchIdx:-1});
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function render(step) {
|
|||
|
|
const s = steps[step];
|
|||
|
|
const arr = temps;
|
|||
|
|
const n = arr.length;
|
|||
|
|
const maxTemp = Math.max(...arr);
|
|||
|
|
const minTemp = Math.min(...arr);
|
|||
|
|
const range = maxTemp - minTemp || 1;
|
|||
|
|
|
|||
|
|
// Temperature bars
|
|||
|
|
let viz = '<div class="temp-bar-container">';
|
|||
|
|
for (let i = 0; i < n; i++) {
|
|||
|
|
const pct = ((arr[i] - minTemp) / range) * 80 + 20;
|
|||
|
|
let barColor = '#93c5fd'; // default
|
|||
|
|
if (i === s.currentIdx) barColor = '#f59e0b';
|
|||
|
|
if (i === s.poppedIdx) barColor = '#ef4444';
|
|||
|
|
if (i === s.matchIdx) barColor = '#22c55e';
|
|||
|
|
if (s.stack.includes(i)) barColor = '#8b5cf6';
|
|||
|
|
|
|||
|
|
viz += `<div class="temp-bar-wrap">`;
|
|||
|
|
viz += `<div class="wait-label">${s.answer[i] > 0 ? s.answer[i] : ''}</div>`;
|
|||
|
|
viz += `<div class="temp-label" style="color:${i===s.currentIdx?'#f59e0b':i===s.poppedIdx?'#ef4444':'var(--text)'};">${arr[i]}°</div>`;
|
|||
|
|
viz += `<div class="temp-bar" style="height:${pct}%;background:${barColor};"></div>`;
|
|||
|
|
viz += `<div class="index-label">${i}</div>`;
|
|||
|
|
viz += '</div>';
|
|||
|
|
}
|
|||
|
|
viz += '</div>';
|
|||
|
|
|
|||
|
|
// Monotone stack
|
|||
|
|
viz += '<div style="margin-top:10px;"><b>单调栈（存索引，对应温度递减）：</b>';
|
|||
|
|
viz += renderStack(s.stack.map(i => `${i}(${arr[i]}°)`), {topIndex: s.stack.length - 1});
|
|||
|
|
viz += '</div>';
|
|||
|
|
|
|||
|
|
// Answer array
|
|||
|
|
const hl = {};
|
|||
|
|
if (s.currentIdx >= 0) hl[s.currentIdx] = 'orange';
|
|||
|
|
if (s.poppedIdx >= 0) hl[s.poppedIdx] = 'red';
|
|||
|
|
if (s.matchIdx >= 0) hl[s.matchIdx] = 'green';
|
|||
|
|
viz += '<div style="margin-top:10px;"><b>答案数组：</b>';
|
|||
|
|
viz += renderArray(s.answer, {highlights: hl});
|
|||
|
|
viz += '</div>';
|
|||
|
|
|
|||
|
|
$('vizArea').innerHTML = viz;
|
|||
|
|
|
|||
|
|
let detail = `<div class="calc-block">${s.msg}</div>`;
|
|||
|
|
detail += '<div style="margin-top:4px;font-size:12px;color:var(--text-secondary);">核心：单调递减栈，遇到更高温度则弹出并计算天数差</div>';
|
|||
|
|
$('detailContent').innerHTML = detail;
|
|||
|
|
|
|||
|
|
if (s.stage === 'done') {
|
|||
|
|
$('resultContent').innerHTML = `<div class="final-answer">返回 <b>[${s.answer.join(', ')}]</b><br>时间复杂度 O(n)，空间 O(n)</div>`;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
$('hintText').textContent = s.msg;
|
|||
|
|
const stages = ['init→初始化','push→入栈','pop→弹出','remaining→剩余','done→完成'];
|
|||
|
|
$('pipeline').innerHTML = stages.map(st => {
|
|||
|
|
const [k,l] = st.split('→');
|
|||
|
|
return `<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 = 'temperatures=[73,74,75,71,69,72,76,73]';
|
|||
|
|
|
|||
|
|
buildSteps(examples[0].temps);
|
|||
|
|
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 m = $('inputArea').value.match(/temperatures=\[([^\]]+)\]/);
|
|||
|
|
if (!m) { alert('格式: temperatures=[73,74,75,71,69,72,76,73]'); return; }
|
|||
|
|
const arr = m[1].split(',').map(Number);
|
|||
|
|
buildSteps(arr);
|
|||
|
|
stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
|||
|
|
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
|||
|
|
} catch(e) { alert('输入格式错误'); }
|
|||
|
|
};
|
|||
|
|
$('exampleSelect').onchange = () => {
|
|||
|
|
const e = examples[parseInt($('exampleSelect').value)];
|
|||
|
|
$('inputArea').value = `temperatures=[${e.temps}]`;
|
|||
|
|
buildSteps(e.temps);
|
|||
|
|
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 dailyTemperatures(temperatures):
|
|||
|
|
n = len(temperatures)
|
|||
|
|
answer = [0] * n
|
|||
|
|
stack = [] # 单调递减栈，存索引
|
|||
|
|
for i, t in enumerate(temperatures):
|
|||
|
|
while stack and t > temperatures[stack[-1]]:
|
|||
|
|
idx = stack.pop()
|
|||
|
|
answer[idx] = i - idx
|
|||
|
|
stack.append(i)
|
|||
|
|
return answer`, {lang:'Python'});
|
|||
|
|
})();
|
|||
|
|
</script>
|
|||
|
|
</body>
|
|||
|
|
</html>
|