栈和排序，牛客习题总结

第一个是我自己的代码。

我一直没看出来自己错哪了

int main() {
	int n;
	std::cin >> n;
	std::vector<int>a(n), b(n);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		b[i] = a[i];
	}
	std::sort(a.begin(), a.end(), [&](int a, int b) {
		return a > b;
		});
	std::stack<int>s;
	int p = 0;
	for (int i = 0; i < n; i++) {
		s.push(b[i]);
		while (!s.empty() && s.top() == a[p]) {
			s.pop();
			p++;
		}
	}
	for (int i = 0; i < p; i++) {
		if (i == n - 1)std::cout << a[i];
		else std::cout << a[i] << ' ';

	}
	while (!s.empty()) {
		std::cout << s.top();
		if (s.size() > 1)std::cout << ' ';
		s.pop();
	}
	return 0;
}

后面大佬给了一个例子3 2 4 1这个序列，用我的代码跑出来是4 1?2?3

而正确答案是4 2 3 1

这是为什么呢，在我的代码里会按顺序找大的，比如先找4再找3，如果找不到3就不会去找2，所以结果的顺序是这样的，3进栈，2进栈，4进然后出，1进栈，然后按出栈直到栈空得出4 1 2 3，这显然是不对的。

由于栈的特性，前面没有出栈的元素显然要等到后进的元素出栈才行，所以当前元素是否出栈要看它是否是它和它后面的序列所有元素中所能找到的最大值，及我们只要算出每个元素后序元素中的最大值，来判断当前元素是否出栈。当它就是目前元素的最大值，那么出栈就能提供最多的贡献

using namespace std;
const int N = 1e6 + 10;
int st[N], tt;
int a[N], maxa[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    //从后往前找到最大的元素
    for (int i = n - 1; i; i--) maxa[i] = max(a[i], maxa[i + 1]);
    for (int i = 0; i < n; i++) {
        //从前向后遍历，maxa[i]表示i后面最大的元素，如果st[tt]比它大，就说明它是目前最大的元素，输出它
        //显然如果它不是最大的元素，那么找到后面那个最大元素再输出时字典序才是最大的，如果你提前输出了，
        while (tt && st[tt] > maxa[i]) {
            cout << st[tt] << ' ';
            tt--;
        }
        st[++tt] = a[i];
    }
    while (st[tt]) {
        cout << st[tt] << ' ';
        tt--;
    }
    return 0;
}