2024-12-30 11:01 哈尔滨理工大学 算法工程师 发布于黑龙江
关注
栈解决问题
给出一个数列 A，求出一个数列B.
其中Bi 表示 数列A中 Ai 右边第一个比 Ai 大的数的下标(从1开始计数),没有找到这一个下标 Bi 就为0
输出数列B
输入描述:
第一行1个数字 n (n ≤ 10000)
第二行n个数字第 i 个数字为 Ai (0 ≤ Ai ≤ 1000000000)
输出描述:
一共一行，第 i 个数和第 i+1 个数中间用空格隔开.
示例1
输入
复制
6
3 2 6 1 1 2
输出
复制
3 3 0 6 6 0
说明
样例不用解释
以下是实现该功能的 C++ 代码：
cpp
#include
#include
#include
using namespace std;
int main() {
int n;
cin >> n;
vector A(n);
for (int i = 0; i < n; ++i) {
cin >> A[i];
}
vector B(n);
stack s;
for (int i = n - 1; i >= 0; --i) {
while (!s.empty() && A[s.top()] <= A[i]) {
s.pop();
}
if (s.empty()) {
B[i] = 0;
} else {
B[i] = s.top() + 1;
}
s.push(i);
}
for (int i = 0; i < n; ++i) {
cout << B[i] << " ";
}
return 0;
}
以下是对代码的解释：
整体思路
利用栈来解决这个问题。从右到左遍历数组 A，对于每个元素 A[i]，将栈顶元素与 A[i] 比较，如果栈顶元素小于等于 A[i]，则弹出栈顶元素，直到栈为空或者栈顶元素大于 A[i]。如果栈为空，说明 A[i] 右侧没有比它大的元素，B[i] 赋值为 0；如果栈不为空，栈顶元素的下标加 1 就是 B[i] 的值，最后将 i 压入栈中。
代码实现细节
首先读取输入的 n 和数组 A。
创建一个与 A 大小相同的数组 B 用于存储结果，以及一个栈 s。
从数组 A 的末尾开始向前遍历：
进入循环 while (!s.empty() && A[s.top()] <= A[i])，不断弹出栈顶元素，直到栈为空或者栈顶元素大于 A[i]。
根据栈的情况确定 B[i] 的值，如果栈为空，B[i] = 0；否则 B[i] = s.top() + 1。
将当前索引 i 压入栈中，以便后续处理。
最后遍历数组 B 并输出结果。
其中Bi 表示 数列A中 Ai 右边第一个比 Ai 大的数的下标(从1开始计数),没有找到这一个下标 Bi 就为0
输出数列B
输入描述:
第一行1个数字 n (n ≤ 10000)
第二行n个数字第 i 个数字为 Ai (0 ≤ Ai ≤ 1000000000)
输出描述:
一共一行，第 i 个数和第 i+1 个数中间用空格隔开.
示例1
输入
复制
6
3 2 6 1 1 2
输出
复制
3 3 0 6 6 0
说明
样例不用解释
以下是实现该功能的 C++ 代码：
cpp
#include
#include
#include
using namespace std;
int main() {
int n;
cin >> n;
vector
for (int i = 0; i < n; ++i) {
cin >> A[i];
}
vector
stack
for (int i = n - 1; i >= 0; --i) {
while (!s.empty() && A[s.top()] <= A[i]) {
s.pop();
}
if (s.empty()) {
B[i] = 0;
} else {
B[i] = s.top() + 1;
}
s.push(i);
}
for (int i = 0; i < n; ++i) {
cout << B[i] << " ";
}
return 0;
}
以下是对代码的解释：
整体思路
利用栈来解决这个问题。从右到左遍历数组 A，对于每个元素 A[i]，将栈顶元素与 A[i] 比较，如果栈顶元素小于等于 A[i]，则弹出栈顶元素，直到栈为空或者栈顶元素大于 A[i]。如果栈为空，说明 A[i] 右侧没有比它大的元素，B[i] 赋值为 0；如果栈不为空，栈顶元素的下标加 1 就是 B[i] 的值，最后将 i 压入栈中。
代码实现细节
首先读取输入的 n 和数组 A。
创建一个与 A 大小相同的数组 B 用于存储结果，以及一个栈 s。
从数组 A 的末尾开始向前遍历：
进入循环 while (!s.empty() && A[s.top()] <= A[i])，不断弹出栈顶元素，直到栈为空或者栈顶元素大于 A[i]。
根据栈的情况确定 B[i] 的值，如果栈为空，B[i] = 0；否则 B[i] = s.top() + 1。
将当前索引 i 压入栈中，以便后续处理。
最后遍历数组 B 并输出结果。
全部评论
相关推荐
2024-12-24 00:45
吉林大学 Java 点赞 评论 收藏
分享