503. Next Greater Element II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res;
        for(int i=0;i<nums.size();++i) {
            int idx = -2;
            for(int j=0;j<nums.size();++j) {
                if (nums[j]>nums[i]) {
                    if (j < i && idx < 0) {
                        idx = j;
                    } else if (j > i) {
                        idx = j;
                        break;
                    }
                }
            }
            
            if (idx < 0)
                res.push_back(-1);
            else
                res.push_back(nums[idx]);
        }
        return res;
    }
};

#define MAX_NUMS 10000

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        bitset<MAX_NUMS> bs;
        stack<int> s;
        
	// 优先右边开始找
        for(int j=nums.size()-1;j>=0;--j) {
	// 从右向左扫描，一定保证栈顶指向元素是最大的，那么就越可能是下一个大的元素
            while (!s.empty() && nums[s.top()] <= nums[j]) s.pop();

            if (!s.empty()) {
                res[j] = nums[s.top()];
		// 标记第一遍已找到的元素
                bs[j] = 1;
            }
            
            s.push(j);
        }
        
	// 没找到的刚好可以利用之前的栈已经存好的从左到右大的元素继续找
        for(int j=nums.size()-1;j>0;--j) {
	   // 只找那些没找到的
            if (bs[j] == 0) {
                while(!s.empty() && nums[j] >= nums[s.top()]) s.pop();
                
                if (!s.empty()) res[j] = nums[s.top()];
            }
        }
        
        return res;
    }
};