c++如何用单调栈找比当前数小的第二个数 给出代码示例

在 C++ 中，可以利用单调栈（Monotonic Stack）数据结构来找到数组中比给定数小的第二个数。单调栈是一种特殊类型的栈，它维护栈元素的顺序，即栈顶始终大于等于（如果堆栈是升序），或者小于等于（如果堆栈是降序）栈底的元素。

以下是使用单调栈解决这个问题的一种常见方法：

#include <iostream>
#include <vector>
using namespace std;

int findSecondLargest(int nums[], int target, int n) {
    if (n <= 0 || nums[0] >= target) return -1; // 如果输入数组为空或第一个数大于等于target，直接返回-1

    stack<int> monoStack;
    for (int i = 0; i < n; ++i) {
        // 如果栈为空，或者新元素大于栈顶元素，入栈
        if (monoStack.empty() || nums[i] > monoStack.top()) {
            monoStack.push(nums[i]);
        } else {
            // 否则，如果新元素小于等于栈顶，将栈顶元素弹出并比较
            while (!monoStack.empty() && nums[i] <= monoStack.top()) {
                monoStack.pop();
            }
            // 若此时栈不为空且栈顶仍大于目标值，说明找到了符合条件的第二大数
            if (!monoStack.empty() && monoStack.top() > target) {
                return monoStack.top();
            }
        }
    }

    // 没有找到满足条件的第二大的数，返回-1
    return -1;
}

int main() {
    int nums[] = {1, 2, 3, 4, 5};
    int target = 3;
    int n = sizeof(nums) / sizeof(nums[0]);

    cout << "The second largest number smaller than " << target << " is: "
         << findSecondLargest(nums, target, n) << endl;

    return 0;
}

在这个例子中，我们遍历数组`nums`，对于每个元素，检查是否需要将栈顶元素替换掉。如果栈顶元素大于目标值`target`，我们就找到了比`target`小的第二大数。如果没有找到这样的数，函数会返回 `-1`。