Leetcode 975

Leetcode 975 odd even jump

题目意思：

给定数组A，分为奇数跳和偶数跳。奇数跳只能跳到比自己大的并且是在比自己大的数字里最小的位置；偶数跳只能跳到比自己小并且是在自己小的数字里最大的位置。要求求出符合要求的起跳起始点的个数。

解法：

单调栈：

注意最枚举的点是起跳点，所以只统计odd数组。
代码来自：https://zhanghuimeng.github.io/post/leetcode-975-odd-even-jump/

class Solution {
public:
    int oddEvenJumps(vector<int>& A) {
        int n = A.size();
        int odd[n], even[n];

        stack<pair<int, int>> s;
        vector<pair<int, int>> indices;
        for (int i = 0; i < n; i++)
            indices.emplace_back(A[i], -i);
        sort(indices.begin(), indices.end());
        for (int i = 0; i < n; i++)
            indices[i].second = -indices[i].second;
        for (int i = 0; i < n; i++) {
            while (!s.empty() && indices[i].second > s.top().second) {
                s.pop();
            }
            if (s.empty())
                even[indices[i].second] = -1;
            else
                even[indices[i].second] = s.top().second;
            s.push(indices[i]);
        }

        s = stack<pair<int, int>>();
        indices.clear();
        for (int i = 0; i < n; i++)
            indices.emplace_back(A[i], i);
        sort(indices.begin(), indices.end());
        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && indices[i].second > s.top().second)
                s.pop();
            if (s.empty())
                odd[indices[i].second] = -1;
            else
                odd[indices[i].second] = s.top().second;
            s.push(indices[i]);
        }

        int oddjump[n], evenjump[n];
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (odd[i] != -1) oddjump[i] = evenjump[odd[i]];
            else oddjump[i] = i;
            if (even[i] != -1) evenjump[i] = oddjump[even[i]];
            else evenjump[i] = i;
            if (oddjump[i] == n - 1) ans++;
        }
        return ans;
    }
};