TB椰程 TypeBuddy 打字搭子

单调栈

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 542 字

维持栈内单调，求左右第一个更大/更小

  • 数据结构
  • 单调栈

前置内容

正文

// 单调栈：栈内元素保持单调
// 常求「左侧/右侧第一个更大」
// 维护递减栈，弹出破坏者
// 例：每日温度（等几天升温）
#include <cstdio>
int a[100005], st[100005], top = 0;
int ans[100005], n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        // 弹出所有 ≤ 当前的
        while (top && a[st[top]] <= a[i]) {
            ans[st[top]] = i - st[top];
            // 记录等待天数
            top--;
        }
        // 当前下标入栈
        st[++top] = i;
    }
    // 仍未升温的输出 0
    for (int i = 1; i <= n; i++)
        if (!ans[i]) printf("0 ");
    return 0;
}

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK