单调栈
发布日期:2021-05-14 16:43:25 浏览次数:17 分类:精选文章

本文共 1045 字,大约阅读时间需要 3 分钟。

为了解决每个数左边第一个比它小的数的问题,我们可以使用栈数据结构。栈的基本思想是:对每个数,检查栈中顶部元素,如果比当前数小,则直接输出;否则,弹出栈顶元素,直到找到比当前数小的元素或者栈为空。最后将当前数压入栈。

步骤如下:

  • 遍历整个数组,依次处理每个元素。
  • 对于每个元素,检查栈顶元素是否比当前元素小。
  • 如果栈顶元素小于当前元素,则当前元素的左边第一个比它小的数即为栈顶元素。
  • 如果栈顶元素大于等于当前元素,则弹出栈顶元素,继续检查后面的元素。
  • 最后将当前元素压入栈。
  • 通过使用栈结构,我们可以高效地解决问题,时间复杂度为O(N)。

    #include 
    #include
    #include
    using namespace std;
    int main() {
    int n;
    cin >> n;
    stack
    s;
    vector
    result(n, -1);
    for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    while (!s.empty() && s.top() >= x) {
    s.pop();
    }
    if (!s.empty()) {
    result[i] = s.top();
    } else {
    result[i] = -1;
    }
    s.push(x);
    }
    // 噢,抱歉,居然忘了这一步,这里的result没有被输出,之前的代码有问题。
    // 这里需要将结果转换为一个string然后输出。修改如下:
    string output;
    for (int num : result) {
    output += to_string(num) + " ";
    }
    // 移除最后一个空格,如果有的话,或者使用其他方法处理。
    if (!output.empty()) {
    output.pop_back();
    }
    cout << output << endl;
    return 0;
    }
    上一篇:单向链表
    下一篇:最长连续不重复子序列

    发表评论

    最新留言

    不错!
    [***.144.177.141]2025年05月02日 03时53分07秒