[LeetCode] Next Greater Element II | 循环数组查找下一个比某位置元素大的

https://leetcode.com/problems/next-greater-element-ii/?tab=Description

思路1：Brute Force

简单粗暴的方法是遍历数组，对每一个位置的元素，往后查找第一个比它大的，走到终点再折回头部查找，直到回到该位置。

Time complexity: O(n^2)
Space complexity: O(1)

ps. 本不报希望，然而leetcode允许该算法通过, C++ 652ms

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        if (nums.empty()) return vector<int>();
        
        int n = nums.size();
        vector<int> ret(n);
        for (int i = 0; i < n; ++i) {
            int next_greater = -1;
            for (int j = (i+1) % n; j != i; j = (j+1) % n) {
                if (nums[j] > nums[i]) {
                    next_greater = nums[j];
                    break;
                }
            }
            ret[i] = next_greater;
        }
        
        return ret;
    }
};

思路2：Stack

单调栈是一种巧妙且有通用意义的技术（比如也可以用在求直方图最大矩形问题里）。开一个栈，先把数组第一个元素的下标压栈（注意是下标），然后从第二个元素开始遍历：

如果遍历到的当前元素大于栈顶，则说明我们发现了栈顶元素的next greater number，记录好结果后pop掉栈顶；并继续考察新的栈顶，重复这个过程；
否则直接把当前元素的下标压栈

举例：数组[2,1,3,5,4]
- 初始栈：[2 （注意实际操作时保留的是元素下标）
- 1比栈顶(2)小，1入栈，栈：[2 1
- 3比栈顶(1)大，1出栈，栈：[2  （记录1的next greater是3）
  - 3比栈顶(2)大，2出栈，栈空  （记录2的next greater是3）
  - 栈空，3入栈，栈：[3
- 5比栈顶(3)大，3出栈，栈空    （记录3的next greater是5）
  - 栈空，5入栈，栈：[5
- 4比栈顶(5)小，4入栈，栈：[5 4

一次遍历完成后，栈中保存的是一个单调不增的序列（从栈底到栈顶），由于题目要求是循环查找，所以再进行第二次遍历，方法和第一次一样，为的是确定还留在栈中的元素的next greater number。第二次遍历结束后还留在栈中的那些可怜的家伙们，就是找不到next greater number的啦

当然，可以把原数组复制一遍连到尾巴上，一次遍历大概也是可以的，不过这样就修改了输入参数。

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        if (nums.empty()) return vector<int>();
        
        int n = nums.size();
        vector<int> ret(n, -1);
        stack<int> stk;
        
        stk.push(0);
        for (int i = 1; i < n; ++i) {
            while (!stk.empty() && nums[i] > nums[ stk.top() ]) {
                ret[ stk.top() ] = nums[i];
                stk.pop();
            }
            stk.push(i);
        }
        for (int i = 0; i < n - 1; ++i) {
            while (!stk.empty() && nums[i] > nums[ stk.top() ]) {
                ret[ stk.top() ] = nums[i];
                stk.pop();
            }
            stk.push(i); 
        }
        
        return ret;
    }
};

ps. leetcode C++ 140ms左右