题目描述
在学校中，N个小朋友站成一队， 第i个小朋友的身高为height[i]，第i个小朋友可以看到的右边的第一个比自己身高更高的小朋友j，那么j是i的好朋友（j > i）。请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用0代替。小朋友人数范围是 [0, 40000]。
输入描述
第一行输入N，表示有N个小朋友
第二行输入N个小朋友的身高height[i]，都是整数
输出描述
输出N个小朋友的好朋友的位置
示例一
输入
2
100 95
输出
0 0
示例二
输入
8
123 124 125 121 119 122 126 123
输出
1 2 6 5 5 6 0 0
题解
类似这种要求寻找左边/右边最近的更大/更小元素的题目 ，都可以使用单调栈 做。
该题是寻找右边最大，正序构建单调栈的做法如下：
/*
* @hw id=2023C lang=java
*
* 找朋友
*/
// @hw code=start
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] height = new int[n];
for(int i=0;i<n;i++) {
height[i] = in.nextInt();
}
List<Integer> stack = new ArrayList<>();
int[] ans = new int[n];
for(int i=0;i<n;i++) {
int h = height[i];
while(!stack.isEmpty() && h > height[stack.get(stack.size()-1)]) {
int top = stack.get(stack.size()-1);
stack.remove(stack.size()-1);
ans[top] = i;
}
stack.add(i);
}
for(int i=0;i<n;i++) {
System.out.print(ans[i] + " ");
}
System.out.println();
}
}
// @hw code=end
#
# @hw id=2023C lang=python3
#
# 找朋友
#
# @hw code=start
n = int(input())
height = list(map(int, input().split()))
stack = list()
ans = [0] * n
for i, h in enumerate(height):
while len(stack) > 0 and h > height[stack[-1]]:
top = stack.pop()
ans[top] = i
stack.append(i)
print(" ".join(map(str, ans)))
# @hw code=end
/*
* @hw id=2023C lang=cpp
*
* 找朋友
*/
// @hw code=start
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> height(n);
for(int i=0;i<n;i++) {
cin >> height[i];
}
vector<int> stack;
vector<int> ans(n, 0);
for(int i=0;i<n;i++) {
int h = height[i];
while(stack.size() != 0 && h > height[stack.back()]) {
int top = stack.back();
stack.pop_back();
ans[top] = i;
}
stack.push_back(i);
}
for(int i=0;i<n;i++) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
// @hw code=end
也可以使用逆向构造单调栈去做。
哈哈，每日一题防止被优化