【单调栈】-----【Look Up S】

P2947 [USACO09MAR] Look Up S

题目链接

题目描述

约翰的 $N(1\le N\le 10^5)$ 头奶牛站成一排，奶牛 $i$ 的身高是 $H_i(1\le H_i\le 10^6)$。现在，每只奶牛都在向右看齐。对于奶牛 $i$，如果奶牛 $j$ 满足 $i<j$ 且 $H_i<H_j$，我们可以说奶牛 $i$ 可以仰望奶牛 $j$。 求出每只奶牛离她最近的仰望对象。

输入格式

第 $1$ 行输入 $N$，之后每行输入一个身高 $H_i$。

输出格式

共 $N$ 行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出 $0$。

输入输出样例 #1

输入 #1

6 
3 
2 
6 
1 
1 
2

输出 #1

3 
3 
0 
6 
6 
0

说明/提示

【输入说明】$6$ 头奶牛的身高分别为 3,2,6,1,1,2。

【输出说明】奶牛 1,2 仰望奶牛 3，奶牛 4,5 仰望奶牛 6，奶牛 3 和 6 没有仰望对象。

【数据规模】
对于 $20\%$ 的数据：$1\le N\le 10$；
对于 $50\%$ 的数据：$1\le N\le 10^3$；
对于 $100\%$ 的数据：$1\le N\le 10^5,1\le H_i\le 10^6$。

题解（单调栈）

单调栈原理见本文

一、问题抽象与分析

我们的问题本质是：对于每个位置 $i$，找出 $j>i$ 且 $H_j>H_i$ 的最小 $j$。

这正是一个经典的 “下一个更大元素”（Next Greater Element）问题：

• 每个元素向右寻找第一个比它大的元素；
• 用单调栈可以在 $O(n)$ 时间内高效求解。

---

二、算法思路（单调栈）

我们从右向左遍历整个数组，维护一个单调递减栈（栈中下标对应的身高递减）：

栈的含义：

• 栈中保存的是还没有“被任何左边的奶牛仰望”的奶牛；
• 栈顶始终是右边最靠近的、可能被当前奶牛仰望的候选对象；
• 一旦发现栈顶的奶牛身高 $\le H_i$，就说明它无法成为 $i$ 的仰望对象，弹出。

维护逻辑：

1. 从 $i=n$ 到 $1$ 逆序扫描每头奶牛；

2. 对于每头奶牛：

   • 弹出所有比它矮或一样高的牛（这些牛无法被仰望）；
   • 栈顶的奶牛就是她可以仰望的最近牛（如果栈非空）；
   • 当前奶牛入栈，作为左边牛的候选仰望对象。

---

三、完整代码：

#include <bits/stdc++.h>
using namespace std;int main()
{int n;// 输入奶牛的数量 n（编号从 1 到 n）cin >> n; // 奶牛的身高数组，height[i] 表示第 i 头奶牛的身高（从下标 1 开始）vector<int> height(n + 1); for (int i = 1; i <= n; i++){// 依次读入每头奶牛的身高cin >> height[i]; }// 单调递减栈，栈中存的是奶牛编号（从右往左维护）stack<int> stk;  // answer[i] 表示奶牛 i 最近能仰望的奶牛编号（若无则为 0）               vector<int> answer(n + 1, 0);   // 从右往左扫描每头奶牛for (int i = n; i >= 1; i--){// 弹出所有“不够高”的奶牛，因为它们不可能成为当前奶牛的仰望对象while (!stk.empty() && height[stk.top()] <= height[i]){stk.pop();}// 此时栈顶就是右边第一个比当前奶牛高的奶牛（如果栈不为空）answer[i] = stk.empty() ? 0 : stk.top();// 当前奶牛编号入栈，作为后面奶牛的“潜在仰望对象”stk.push(i);}// 输出答案，每行一个：第 i 行表示第 i 头奶牛仰望的奶牛编号（或者 0）for (int i = 1; i <= n; i++){cout << answer[i] << endl;}return 0;
}

---

四、复杂度分析

• 时间复杂度：每个元素最多入栈一次、出栈一次，复杂度为 $O(n)$；
• 空间复杂度：使用 $O(n)$ 额外空间保存答案和单调栈。

---

五、总结

本题的关键在于右边第一个比它大的元素，这类问题是单调栈的经典应用之一：

类型	维护方向	栈内单调性	典型问题
找右边第一个更大元素	右→左	单调递减	本题 Look Up、柱状图最大矩形
找右边第一个更小元素	右→左	单调递增	维护下一个最小值
找左边第一个更大元素	左→右	单调递减	左边比它大的最近值
找左边第一个更小元素	左→右	单调递增	下一个更小值

---