栈及变种 – 喜新厌旧的渣男

单调栈

PAT-A1101 找枢轴

① 暴力解法:分别向左右查询大小的暴力匹配 $\scriptsize O(n^2)$ 会超时
② 快速排序性质:左侧元素不大于枢轴,右侧元素不小于枢轴,枢轴确定下标时为正确序中的排名,此条性质用在TopK问题中被称为 快速选择算法(Quick Select),因此本题可将序列排序后再与原序列一一比对,比对成功且对应回到原序列左侧无更大值的都是正确的枢轴。复杂度 $\scriptsize O(nlogn)$
③ 改版单调栈:线性问题尽量向一次遍历优化,这就需要遍历过程中利用已知结论。枢轴的性质要求左小右大,也就是要求 每个当前访问数都要比已访问数大,符合单调栈性质。维护一个单增栈,只要比已知最大元素更大就入栈,由此左侧所有数(栈中元素)都比当前元素(栈顶元素)小,满足了“左小性质”。如果当前元素比栈顶小,说明:a)该数不满足“左小”不入栈 b)栈中所有比当前元素大的元素都不满足“右大”性质,需要将其一一出栈。如例 $\scriptsize [1,3,4,2,5]$,读到数 $\scriptsize 2$ 时,$\scriptsize 3、4、2$ 均不满足性质,而 $\scriptsize 1$ 满足要保留。最坏情况 $\scriptsize n-1$ 个元素都要进一次栈、退一次栈,复杂度为 $\scriptsize O(n)$


Q:为什么不是标准单调栈比栈顶更大入栈,而是大于已知max入栈呢?

A:比栈顶更大入栈当然能保证栈的单增性,关键是退栈操作后,可能会存在 栈顶<当前<曾经的左侧最大 情况,如例 $\scriptsize [1,4,2,3,5]$,读到数 $\scriptsize 2$ 时 $\scriptsize 4$ 出栈,读到数 $\scriptsize 3$ 时栈顶元素为 $\scriptsize 1$,忽略了之前的更大数 $\scriptsize 4$

Q:格式错误什么鬼?

A:惊了!数目为0的时候,没有元素,替代输出一个’\n’,题中确实没说明,姥姥是想让我们揣摩她心思嘛?


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

int main() {
    int N, t, preMax = 0;
    vector<int> v;
    scanf("%d", &N);
    while (N--) {
        scanf("%d", &t);
        if (t > preMax) {
            v.push_back(t);
            preMax = t;
        }
        else while (!v.empty() && v.back() > t)
            v.pop_back();
    }

    printf("%d\n", v.size());
    for (int i = 0; i < v.size(); i++)
        if (i == v.size() - 1) printf("%d", v[i]);
        else printf("%d ", v[i]);
    putchar('\n');
    return 0;
}

“栈及变种 – 喜新厌旧的渣男”的一个回复

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

©2018-2024 Howell版权所有 备案号:冀ICP备19000576号